Data Structures Tutorial

Welcome to the Data Structures (DS) Tutorial. In this guide, we will explore the fundamentals of Data Structures, from basic concepts to complex structures and algorithms. By the end, you will have a solid understanding of how to utilize various data structures to solve complex problems efficiently.

DS Introduction

Data Structures are the building blocks of computer science, providing ways to organize, manage, and store data efficiently. Understanding different types of data structures is crucial to solving problems in an optimal way. Common data structures include arrays, linked lists, stacks, queues, and trees.

DS Algorithm

An algorithm is a step-by-step procedure or formula for solving a problem. In the context of data structures, algorithms are used to manipulate the data within those structures. Key concepts in algorithms include searching, sorting, and traversing through data.

{`// Example: Simple Algorithm to find the maximum value in an array
function findMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

// Usage
const numbers = [3, 5, 1, 8, 4];
console.log(findMax(numbers)); // Output: 8`}
    

Asymptotic Analysis

Asymptotic Analysis is a way to describe the performance of an algorithm as the input size grows. The most common notations are Big O (worst case), Big Theta (average case), and Big Omega (best case). Understanding these concepts is vital to analyzing the efficiency of algorithms.

• Big O (O): Describes the upper bound of the algorithm's time complexity.
• Big Omega (Ω): Represents the lower bound of the time complexity.
• Big Theta (Θ): Indicates the average case complexity.

{`// Example: Big O Notation
function example(n) {
  for (let i = 0; i < n; i++) {
    console.log(i); // O(n) - Linear Time Complexity
  }
}`}
    

DS Pointer

A pointer is a variable that stores the memory address of another variable. Pointers are a powerful tool in data structures, allowing for efficient memory management, dynamic allocation, and manipulation of data in C/C++ languages. Pointers are essential when dealing with linked lists, trees, and other complex data structures.

{`// Example: Basic Pointer in C
#include 

int main() {
  int var = 10;
  int *ptr = &var;

  printf("Value of var: %d\\n", var);
  printf("Address of var: %p\\n", ptr);
  printf("Value at ptr: %d\\n", *ptr);

  return 0;
}`}
    

DS Structure

A structure (or struct) is a user-defined data type in C/C++ that groups related variables of different data types. It is useful for organizing data with multiple attributes. Structures are the foundation for creating more complex data types, such as linked lists, trees, and graphs.

{`// Example: Simple Structure in C
#include 

struct Student {
  int id;
  char name[50];
  float grade;
};

int main() {
  struct Student student1;
  student1.id = 101;
  strcpy(student1.name, "John Doe");
  student1.grade = 4.0;

  printf("Student ID: %d\\n", student1.id);
  printf("Student Name: %s\\n", student1.name);
  printf("Student Grade: %.2f\\n", student1.grade);

  return 0;
}`}
    

Arrays

An array is a collection of elements stored in a contiguous memory location. Arrays are one of the simplest and most commonly used data structures, allowing random access to elements using an index. Arrays are widely used for storing data in various applications because of their simplicity and efficiency.

What is an Array?

An array is a linear data structure that can hold a fixed number of elements of the same type. Each element can be accessed by an index, starting from 0. Arrays are particularly useful when you need to store a collection of data, such as a list of numbers or names.

{`// Example: Simple Array in C
#include 

int main() {
  int numbers[5] = {10, 20, 30, 40, 50}; // Array of integers

  // Accessing elements using index
  printf("First element: %d\\n", numbers[0]); // Output: 10
  printf("Third element: %d\\n", numbers[2]); // Output: 30

  // Iterating over the array
  for (int i = 0; i < 5; i++) {
    printf("%d ", numbers[i]);
  }

  return 0;
}`}
    

Operations on Arrays

Common operations on arrays include:

• Traversal: Accessing each element of the array.
• Insertion: Adding an element to the array.
• Deletion: Removing an element from the array.
• Search: Finding an element in the array.
• Update: Modifying an existing element in the array.

{`// Example: Traversing an Array
#include 

int main() {
  int numbers[] = {5, 10, 15, 20, 25};

  // Traversal
  printf("Array elements:\\n");
  for (int i = 0; i < 5; i++) {
    printf("%d ", numbers[i]);
  }

  return 0;
}`}
    

2D Arrays

A 2D array is an array of arrays, also known as a matrix or a table. It consists of rows and columns, making it useful for representing grid-like data such as a chessboard or a spreadsheet. In a 2D array, each element is accessed by two indices: the row and the column.

What is a 2D Array?

A 2D array is a matrix with rows and columns. Each element in a 2D array is accessed by specifying its row and column index. It is declared with two indices, representing the dimensions.

{`// Example: Simple 2D Array in C
#include 

int main() {
  int matrix[3][3] = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
  };

  // Accessing elements using row and column index
  printf("Element at (0, 0): %d\\n", matrix[0][0]); // Output: 1
  printf("Element at (1, 2): %d\\n", matrix[1][2]); // Output: 6

  // Printing the entire matrix
  printf("Matrix:\\n");
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      printf("%d ", matrix[i][j]);
    }
    printf("\\n");
  }

  return 0;
}`}
  

Operations on 2D Arrays

Common operations on 2D arrays include:

• Traversal: Accessing each element of the 2D array row by row or column by column.
• Insertion: Adding an element at a specific position in the matrix.
• Deletion: Removing an element from a specified position.
• Search: Finding an element in the 2D array.
• Update: Changing an existing element in the 2D array.

{`// Example: Traversing a 2D Array
#include 

int main() {
  int matrix[2][3] = {
    {1, 2, 3},
    {4, 5, 6}
  };

  // Traversal by rows
  printf("Matrix elements:\\n");
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 3; j++) {
      printf("%d ", matrix[i][j]);
    }
    printf("\\n");
  }

  return 0;
}`}
  

Linked List

A Linked List is a linear data structure where each element is a separate object called a node. Each node contains data and a reference (or link) to the next node in the sequence. Unlike arrays, linked lists provide dynamic memory allocation, making them ideal for situations where the data size can vary.

Types of Linked Lists

• Singly Linked List
• Doubly Linked List
• Circular Linked List
• Circular Doubly Linked List
• Skip List

Singly Linked List

A Singly Linked List is a type of linked list where each node has two parts: data and a pointer to the next node. It allows for efficient insertion and deletion from the beginning but requires traversal to access any other node.

{`// Example: Singly Linked List in C
#include 
#include 

// Node structure
struct Node {
  int data;
  struct Node* next;
};

// Function to create a new node
struct Node* createNode(int data) {
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->data = data;
  newNode->next = NULL;
  return newNode;
}

// Function to print the linked list
void printList(struct Node* head) {
  struct Node* temp = head;
  while (temp != NULL) {
    printf("%d -> ", temp->data);
    temp = temp->next;
  }
  printf("NULL\\n");
}

int main() {
  struct Node* head = createNode(10);
  head->next = createNode(20);
  head->next->next = createNode(30);

  printf("Singly Linked List:\\n");
  printList(head);

  return 0;
}`}
  

Doubly Linked List

A Doubly Linked List has nodes containing a reference to the next node and the previous node. This bidirectional navigation makes insertion and deletion more efficient at any point in the list.

{`// Example: Doubly Linked List in C
#include 
#include 

// Node structure
struct Node {
  int data;
  struct Node* next;
  struct Node* prev;
};

// Function to create a new node
struct Node* createNode(int data) {
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->data = data;
  newNode->next = NULL;
  newNode->prev = NULL;
  return newNode;
}

// Function to print the linked list
void printList(struct Node* head) {
  struct Node* temp = head;
  while (temp != NULL) {
    printf("%d <-> ", temp->data);
    temp = temp->next;
  }
  printf("NULL\\n");
}

int main() {
  struct Node* head = createNode(10);
  struct Node* second = createNode(20);
  struct Node* third = createNode(30);

  head->next = second;
  second->prev = head;
  second->next = third;
  third->prev = second;

  printf("Doubly Linked List:\\n");
  printList(head);

  return 0;
}`}
  

Circular Linked List

A Circular Linked List is a linked list where the last node points back to the first node, forming a loop. This type of list is useful for tasks that require cycling through data repeatedly.

{`// Example: Circular Linked List in C
#include 
#include 

// Node structure
struct Node {
  int data;
  struct Node* next;
};

// Function to create a new node
struct Node* createNode(int data) {
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->data = data;
  newNode->next = NULL;
  return newNode;
}

// Function to print the circular linked list
void printList(struct Node* head) {
  struct Node* temp = head;
  if (head != NULL) {
    do {
      printf("%d -> ", temp->data);
      temp = temp->next;
    } while (temp != head);
  }
  printf("HEAD\\n");
}

int main() {
  struct Node* head = createNode(10);
  struct Node* second = createNode(20);
  struct Node* third = createNode(30);

  head->next = second;
  second->next = third;
  third->next = head; // Creating circular link

  printf("Circular Linked List:\\n");
  printList(head);

  return 0;
}`}
  

Circular Doubly Linked List

A Circular Doubly Linked List combines features of doubly and circular linked lists. Each node has links to both the next and previous nodes, and the last node links back to the first, creating a circular structure.

{`// Example: Circular Doubly Linked List in C
#include 
#include 

// Node structure
struct Node {
  int data;
  struct Node* next;
  struct Node* prev;
};

// Function to create a new node
struct Node* createNode(int data) {
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->data = data;
  newNode->next = NULL;
  newNode->prev = NULL;
  return newNode;
}

// Function to print the circular doubly linked list
void printList(struct Node* head) {
  struct Node* temp = head;
  if (head != NULL) {
    do {
      printf("%d <-> ", temp->data);
      temp = temp->next;
    } while (temp != head);
  }
  printf("HEAD\\n");
}

int main() {
  struct Node* head = createNode(10);
  struct Node* second = createNode(20);
  struct Node* third = createNode(30);

  head->next = second;
  second->prev = head;
  second->next = third;
  third->prev = second;
  third->next = head; // Creating circular link
  head->prev = third;

  printf("Circular Doubly Linked List:\\n");
  printList(head);

  return 0;
}`}
  

Skip List

A Skip List is an advanced data structure built on top of a linked list, with multiple layers of linked lists. These layers allow for fast searches, inserts, and deletions by "skipping" over sections of the list, much like a balanced tree.

Skip lists are commonly used in scenarios that require fast search times, similar to binary search trees but with simpler implementation.

{`// Basic idea of Skip List (in pseudocode)
struct Node {
  int data;
  struct Node* forward[]; // Array of pointers (forward links for skipping)
};

// A simplified example showing structure; real skip lists involve complex probabilistic balancing
`}
  

Stack

A Stack is a linear data structure that follows the Last In, First Out (LIFO) principle. In a stack, elements are added (pushed) and removed (popped) from the same end, called the top. It is commonly used in situations where data needs to be processed in a reverse order, like undo operations, backtracking algorithms, or parsing expressions.

• Array-based Stack Implementation
• Linked List-based Stack Implementation

Array-based Stack Implementation

In the Array-based Stack, a fixed-size array is used to store the stack elements. The top of the stack is tracked using an index that moves as elements are pushed or popped. This implementation is simple and efficient, but its size is limited by the predefined array capacity.

{`// Example: Array-based Stack in C
#include 
#include 

#define MAX 5  // Maximum size of the stack

struct Stack {
  int data[MAX];
  int top;
};

// Initialize the stack
void initialize(struct Stack* stack) {
  stack->top = -1;
}

// Check if the stack is empty
int isEmpty(struct Stack* stack) {
  return stack->top == -1;
}

// Check if the stack is full
int isFull(struct Stack* stack) {
  return stack->top == MAX - 1;
}

// Push an element onto the stack
void push(struct Stack* stack, int value) {
  if (isFull(stack)) {
    printf("Stack Overflow!\\n");
  } else {
    stack->data[++(stack->top)] = value;
    printf("%d pushed onto stack\\n", value);
  }
}

// Pop an element from the stack
int pop(struct Stack* stack) {
  if (isEmpty(stack)) {
    printf("Stack Underflow!\\n");
    return -1;
  } else {
    return stack->data[(stack->top)--];
  }
}

// Print the stack elements
void printStack(struct Stack* stack) {
  if (isEmpty(stack)) {
    printf("Stack is empty.\\n");
  } else {
    printf("Stack elements: ");
    for (int i = 0; i <= stack->top; i++) {
      printf("%d ", stack->data[i]);
    }
    printf("\\n");
  }
}

int main() {
  struct Stack stack;
  initialize(&stack);

  push(&stack, 10);
  push(&stack, 20);
  push(&stack, 30);
  printStack(&stack);

  printf("Popped: %d\\n", pop(&stack));
  printStack(&stack);

  return 0;
}`}
  

Linked List-based Stack Implementation

In the Linked List-based Stack, each element is a node containing data and a reference to the next node. The stack is dynamic, meaning it can grow or shrink as needed, limited only by system memory. This implementation is more flexible than an array-based stack.

{`// Example: Linked List-based Stack in C
#include 
#include 

// Node structure
struct Node {
  int data;
  struct Node* next;
};

// Function to create a new node
struct Node* createNode(int data) {
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->data = data;
  newNode->next = NULL;
  return newNode;
}

// Push an element onto the stack
void push(struct Node** top, int value) {
  struct Node* newNode = createNode(value);
  newNode->next = *top;
  *top = newNode;
  printf("%d pushed onto stack\\n", value);
}

// Pop an element from the stack
int pop(struct Node** top) {
  if (*top == NULL) {
    printf("Stack Underflow!\\n");
    return -1;
  } else {
    struct Node* temp = *top;
    int poppedValue = temp->data;
    *top = (*top)->next;
    free(temp);
    return poppedValue;
  }
}

// Print the stack elements
void printStack(struct Node* top) {
  if (top == NULL) {
    printf("Stack is empty.\\n");
  } else {
    printf("Stack elements: ");
    struct Node* temp = top;
    while (temp != NULL) {
      printf("%d ", temp->data);
      temp = temp->next;
    }
    printf("\\n");
  }
}

int main() {
  struct Node* stack = NULL;

  push(&stack, 10);
  push(&stack, 20);
  push(&stack, 30);
  printStack(stack);

  printf("Popped: %d\\n", pop(&stack));
  printStack(stack);

  return 0;
}`}
  

Queues

A Queue is a linear data structure that follows the First In, First Out (FIFO) principle. Elements are inserted from the rear (end) and removed from the front. Queues are used in various scenarios, such as scheduling tasks, handling requests in web servers, and breadth-first traversal in graphs.

Types of Queues

There are several types of queues that extend the basic concept:

• Simple Queue: Standard FIFO queue where insertion is done at the rear and deletion at the front.
• Circular Queue: A queue that connects the rear to the front, forming a circle. It helps utilize memory more efficiently.
• Priority Queue: Each element has a priority. Elements are dequeued based on priority rather than insertion order.
• Double-ended Queue (Deque): Allows insertion and deletion at both the front and the rear.

Queue Implementation Using Arrays

A queue can be implemented using an array where the rear and front pointers are used to track the insertion and deletion positions. This method is simple but has a limitation with a fixed size.

{`// Example: Queue Implementation Using Array in C
#include 
#define MAX 5

int queue[MAX];
int front = -1, rear = -1;

// Function to check if the queue is empty
int isEmpty() {
  return front == -1;
}

// Function to check if the queue is full
int isFull() {
  return rear == MAX - 1;
}

// Enqueue (Add) an element to the queue
void enqueue(int value) {
  if (isFull()) {
    printf("Queue is full!\\n");
  } else {
    if (front == -1) front = 0;
    queue[++rear] = value;
    printf("Enqueued: %d\\n", value);
  }
}

// Dequeue (Remove) an element from the queue
void dequeue() {
  if (isEmpty()) {
    printf("Queue is empty!\\n");
  } else {
    printf("Dequeued: %d\\n", queue[front]);
    if (front >= rear) {
      front = rear = -1;
    } else {
      front++;
    }
  }
}

// Display the elements of the queue
void displayQueue() {
  if (isEmpty()) {
    printf("Queue is empty!\\n");
  } else {
    printf("Queue: ");
    for (int i = front; i <= rear; i++) {
      printf("%d ", queue[i]);
    }
    printf("\\n");
  }
}

int main() {
  enqueue(10);
  enqueue(20);
  enqueue(30);
  dequeue();
  displayQueue();
  return 0;
}`}
  

Queue Implementation Using Linked List

A queue can also be implemented using a linked list, providing a dynamic size that avoids the limitations of a fixed-size array. The front and rear pointers are used to manage the queue.

{`// Example: Queue Implementation Using Linked List in C
#include 
#include 

// Define a node in the linked list
struct Node {
  int data;
  struct Node* next;
};

// Define the front and rear of the queue
struct Node* front = NULL;
struct Node* rear = NULL;

// Enqueue (Add) an element to the queue
void enqueue(int value) {
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->data = value;
  newNode->next = NULL;

  if (rear == NULL) {
    front = rear = newNode;
  } else {
    rear->next = newNode;
    rear = newNode;
  }
  printf("Enqueued: %d\\n", value);
}

// Dequeue (Remove) an element from the queue
void dequeue() {
  if (front == NULL) {
    printf("Queue is empty!\\n");
    return;
  }

  struct Node* temp = front;
  front = front->next;

  if (front == NULL) {
    rear = NULL;
  }

  printf("Dequeued: %d\\n", temp->data);
  free(temp);
}

// Display the elements of the queue
void displayQueue() {
  if (front == NULL) {
    printf("Queue is empty!\\n");
  } else {
    struct Node* temp = front;
    printf("Queue: ");
    while (temp != NULL) {
      printf("%d ", temp->data);
      temp = temp->next;
    }
    printf("\\n");
  }
}

int main() {
  enqueue(5);
  enqueue(15);
  enqueue(25);
  dequeue();
  displayQueue();
  return 0;
}`}
  

Circular Queue

A Circular Queue is a type of queue in which the last position is connected back to the first position to form a circle. It overcomes the limitations of a simple queue by reusing the empty space left by dequeued elements. Circular queues are implemented using arrays and are more memory-efficient than linear queues.

{`// Example: Circular Queue Implementation in C
#include 
#define SIZE 5

int queue[SIZE];
int front = -1, rear = -1;

// Function to check if the queue is full
int isFull() {
  return (front == 0 && rear == SIZE - 1) || (front == rear + 1);
}

// Function to check if the queue is empty
int isEmpty() {
  return front == -1;
}

// Enqueue (Add) an element to the circular queue
void enqueue(int value) {
  if (isFull()) {
    printf("Circular Queue is full!\\n");
  } else {
    if (front == -1) front = 0;
    rear = (rear + 1) % SIZE;
    queue[rear] = value;
    printf("Enqueued: %d\\n", value);
  }
}

// Dequeue (Remove) an element from the circular queue
void dequeue() {
  if (isEmpty()) {
    printf("Circular Queue is empty!\\n");
  } else {
    printf("Dequeued: %d\\n", queue[front]);
    if (front == rear) {
      front = rear = -1;
    } else {
      front = (front + 1) % SIZE;
    }
  }
}

// Display the elements of the circular queue
void displayQueue() {
  if (isEmpty()) {
    printf("Circular Queue is empty!\\n");
  } else {
    printf("Circular Queue: ");
    int i = front;
    while (1) {
      printf("%d ", queue[i]);
      if (i == rear) break;
      i = (i + 1) % SIZE;
    }
    printf("\\n");
  }
}

int main() {
  enqueue(10);
  enqueue(20);
  enqueue(30);
  dequeue();
  displayQueue();
  return 0;
}`}
  

Deque (Double-ended Queue)

A Deque (Double-ended Queue) is a linear data structure that allows insertion and deletion from both ends—front and rear. It can operate as both a queue (FIFO) and a stack (LIFO), making it a versatile data structure for various use cases.

    // Example: Deque Implementation in C
    #include <stdio.h>
    #define SIZE 5

    int deque[SIZE];
    int front = -1, rear = -1;

    // Function to check if the deque is full
    int isFull() {
      return (front == 0 && rear == SIZE - 1) || (front == rear + 1);
    }

    // Function to check if the deque is empty
    int isEmpty() {
      return front == -1;
    }

    // Insert element at the front
    void insertFront(int value) {
      if (isFull()) {
        printf("Deque is full!\\n");
      } else {
        if (front == -1) {
          front = rear = 0;
        } else if (front == 0) {
          front = SIZE - 1;
        } else {
          front--;
        }
        deque[front] = value;
        printf("Inserted at front: %d\\n", value);
      }
    }

    // Insert element at the rear
    void insertRear(int value) {
      if (isFull()) {
        printf("Deque is full!\\n");
      } else {
        if (front == -1) {
          front = rear = 0;
        } else if (rear == SIZE - 1) {
          rear = 0;
        } else {
          rear++;
        }
        deque[rear] = value;
        printf("Inserted at rear: %d\\n", value);
      }
    }

    // Remove element from the front
    void deleteFront() {
      if (isEmpty()) {
        printf("Deque is empty!\\n");
      } else {
        printf("Removed from front: %d\\n", deque[front]);
        if (front == rear) {
          front = rear = -1;
        } else if (front == SIZE - 1) {
          front = 0;
        } else {
          front++;
        }
      }
    }

    // Remove element from the rear
    void deleteRear() {
      if (isEmpty()) {
        printf("Deque is empty!\\n");
      } else {
        printf("Removed from rear: %d\\n", deque[rear]);
        if (front == rear) {
          front = rear = -1;
        } else if (rear == 0) {
          rear = SIZE - 1;
        } else {
          rear--;
        }
      }
    }

    // Display the elements of the deque
    void displayDeque() {
      if (isEmpty()) {
        printf("Deque is empty!\\n");
      } else {
        printf("Deque: ");
        int i = front;
        while (1) {
          printf("%d ", deque[i]);
          if (i == rear) break;
          i = (i + 1) % SIZE;
        }
        printf("\\n");
      }
    }

    int main() {
      insertRear(10);
      insertFront(20);
      deleteFront();
      displayDeque();
      return 0;
    }
  

Priority Queue

A Priority Queue is a special type of queue where each element is associated with a priority. Elements with higher priority are dequeued before elements with lower priority. If two elements have the same priority, they follow the standard FIFO order.

    // Example: Priority Queue Implementation in C
    #include <stdio.h>
    #define SIZE 5

    struct PriorityQueue {
      int data;
      int priority;
    };

    struct PriorityQueue pq[SIZE];
    int rear = -1;

    // Function to check if the priority queue is empty
    int isEmpty() {
      return rear == -1;
    }

    // Function to check if the priority queue is full
    int isFull() {
      return rear == SIZE - 1;
    }

    // Enqueue element based on priority
    void enqueue(int value, int priority) {
      if (isFull()) {
        printf("Priority Queue is full!\\n");
      } else {
        rear++;
        pq[rear].data = value;
        pq[rear].priority = priority;
        printf("Enqueued: %d with priority %d\\n", value, priority);

        // Sort the queue based on priority
        for (int i = 0; i <= rear; i++) {
          for (int j = i + 1; j <= rear; j++) {
            if (pq[i].priority > pq[j].priority) {
              struct PriorityQueue temp = pq[i];
              pq[i] = pq[j];
              pq[j] = temp;
            }
          }
        }
      }
    }

    // Dequeue the highest priority element
    void dequeue() {
      if (isEmpty()) {
        printf("Priority Queue is empty!\\n");
      } else {
        printf("Dequeued: %d with priority %d\\n", pq[0].data, pq[0].priority);

        // Shift elements to the left
        for (int i = 0; i < rear; i++) {
          pq[i] = pq[i + 1];
        }
        rear--;
      }
    }

    // Display the priority queue
    void displayPriorityQueue() {
      if (isEmpty()) {
        printf("Priority Queue is empty!\\n");
      } else {
        printf("Priority Queue: ");
        for (int i = 0; i <= rear; i++) {
          printf("(%d, priority %d) ", pq[i].data, pq[i].priority);
        }
        printf("\\n");
      }
    }

    int main() {
      enqueue(10, 2);
      enqueue(20, 1);
      enqueue(30, 3);
      dequeue();
      displayPriorityQueue();
      return 0;
    }
  

Data Structures: Trees

Introduction to Trees

A Tree is a hierarchical data structure that consists of nodes connected by edges. A tree has a root node, branches, and leaf nodes. It is used to represent data in a structured way, such as file systems, XML parsing, and more. Each tree node contains a value and pointers to its child nodes.

Trees are non-linear structures, which means that data is not stored sequentially. Common types of trees include Binary Trees, Binary Search Trees (BST), AVL Trees, and more.

Binary Tree

A Binary Tree is a type of tree in which each node has at most two children, commonly referred to as the left and right child. Binary trees are used in various applications like expression parsing, decision-making processes, and representing hierarchical data.

// Example: Basic Binary Tree Implementation in C
#include <stdio.h>
#include <stdlib.h>

// Definition of the binary tree node
struct Node {
  int data;
  struct Node* left;
  struct Node* right;
};

// Function to create a new node
struct Node* createNode(int data) {
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->data = data;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}

// Function to insert a node in a binary tree
struct Node* insertNode(struct Node* root, int data) {
  if (root == NULL) {
    root = createNode(data);
  } else if (data <= root->data) {
    root->left = insertNode(root->left, data);
  } else {
    root->right = insertNode(root->right, data);
  }
  return root;
}

// In-order traversal of the binary tree
void inorderTraversal(struct Node* root) {
  if (root != NULL) {
    inorderTraversal(root->left);
    printf("%d ", root->data);
    inorderTraversal(root->right);
  }
}

int main() {
  struct Node* root = NULL;
  root = insertNode(root, 10);
  insertNode(root, 5);
  insertNode(root, 15);
  insertNode(root, 2);
  insertNode(root, 7);
  
  printf("In-order Traversal: ");
  inorderTraversal(root);
  return 0;
}

  

In the example above, a simple binary tree is created with nodes containing integer values. The tree is traversed using In-order traversal, which visits nodes in the following order: left subtree, root, and then right subtree.

Binary Search Tree (BST)

A Binary Search Tree (BST) is a special type of binary tree that maintains the property where the left child of a node contains a value less than the parent node, and the right child contains a value greater than the parent node. This property allows for efficient searching, insertion, and deletion operations.

// Example: Binary Search Tree (BST) Implementation in C
#include <stdio.h>
#include <stdlib.h>

// Definition of the BST node
struct Node {
  int data;
  struct Node* left;
  struct Node* right;
};

// Function to create a new node
struct Node* createNode(int data) {
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->data = data;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}

// Function to insert a node in a BST
struct Node* insertNode(struct Node* root, int data) {
  if (root == NULL) {
    root = createNode(data);
  } else if (data < root->data) {
    root->left = insertNode(root->left, data);
  } else {
    root->right = insertNode(root->right, data);
  }
  return root;
}

// Function to search for a node in a BST
struct Node* searchNode(struct Node* root, int data) {
  if (root == NULL || root->data == data) {
    return root;
  } else if (data < root->data) {
    return searchNode(root->left, data);
  } else {
    return searchNode(root->right, data);
  }
}

// In-order traversal of the BST
void inorderTraversal(struct Node* root) {
  if (root != NULL) {
    inorderTraversal(root->left);
    printf("%d ", root->data);
    inorderTraversal(root->right);
  }
}

int main() {
  struct Node* root = NULL;
  root = insertNode(root, 20);
  insertNode(root, 10);
  insertNode(root, 30);
  insertNode(root, 5);
  insertNode(root, 15);
  
  printf("In-order Traversal of BST: ");
  inorderTraversal(root);
  
  // Searching for a value
  int searchValue = 15;
  if (searchNode(root, searchValue) != NULL) {
    printf("\\nValue %d found in the BST.\\n", searchValue);
  } else {
    printf("\\nValue %d not found in the BST.\\n", searchValue);
  }
  return 0;
}

  

The code above demonstrates a Binary Search Tree with basic operations such as insertion and searching. In a BST, the left subtree contains values smaller than the root, while the right subtree contains larger values, making it efficient for search operations.

AVL Tree

An AVL Tree is a self-balancing Binary Search Tree (BST) where the difference in heights between the left and right subtrees of any node is at most 1. To maintain this balance, rotations (single or double) are used when inserting or deleting nodes.

// Example: AVL Tree Implementation in C
#include <stdio.h>
#include <stdlib.h>

// Node structure for AVL Tree
struct Node {
  int data;
  struct Node* left;
  struct Node* right;
  int height;
};

// Function to get the height of a node
int height(struct Node* node) {
  if (node == NULL) return 0;
  return node->height;
}

// Function to create a new node
struct Node* createNode(int data) {
  struct Node* node = (struct Node*)malloc(sizeof(struct Node));
  node->data = data;
  node->left = node->right = NULL;
  node->height = 1; // new node is initially at height 1
  return node;
}

// Function to get the balance factor of a node
int getBalance(struct Node* node) {
  if (node == NULL) return 0;
  return height(node->left) - height(node->right);
}

// Right rotation utility
struct Node* rightRotate(struct Node* y) {
  struct Node* x = y->left;
  struct Node* T2 = x->right;
  
  x->right = y;
  y->left = T2;
  
  y->height = 1 + max(height(y->left), height(y->right));
  x->height = 1 + max(height(x->left), height(x->right));
  
  return x;
}

// Left rotation utility
struct Node* leftRotate(struct Node* x) {
  struct Node* y = x->right;
  struct Node* T2 = y->left;
  
  y->left = x;
  x->right = T2;
  
  x->height = 1 + max(height(x->left), height(x->right));
  y->height = 1 + max(height(y->left), height(y->right));
  
  return y;
}

// Function to insert a node in AVL Tree
struct Node* insertNode(struct Node* node, int data) {
  if (node == NULL) return createNode(data);
  
  if (data < node->data)
    node->left = insertNode(node->left, data);
  else if (data > node->data)
    node->right = insertNode(node->right, data);
  else
    return node;
  
  node->height = 1 + max(height(node->left), height(node->right));
  int balance = getBalance(node);
  
  // Balance the tree using rotations
  if (balance > 1 && data < node->left->data)
    return rightRotate(node);
  if (balance < -1 && data > node->right->data)
    return leftRotate(node);
  if (balance > 1 && data > node->left->data) {
    node->left = leftRotate(node->left);
    return rightRotate(node);
  }
  if (balance < -1 && data < node->right->data) {
    node->right = rightRotate(node->right);
    return leftRotate(node);
  }
  
  return node;
}

  

The code example demonstrates the insertion of nodes in an AVL Tree with rotations to maintain balance. Rotations include left, right, and combinations like left-right and right-left.

B Tree

A B Tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. It is primarily used in databases and file systems where large blocks of data are read.

// Example: B Tree Node Structure in C
#define MAX 3 // Maximum number of children for demonstration
#define MIN 2 // Minimum degree of the B Tree

struct BTreeNode {
  int data[MAX + 1]; // Data in nodes
  struct BTreeNode* children[MAX + 1]; // Children pointers
  int count; // Number of keys in node
};

struct BTreeNode* root;

// Function to create a new B Tree node
struct BTreeNode* createNode(int data, struct BTreeNode* child) {
  struct BTreeNode* newNode;
  newNode = (struct BTreeNode*)malloc(sizeof(struct BTreeNode));
  newNode->data[1] = data;
  newNode->count = 1;
  newNode->children[0] = root;
  newNode->children[1] = child;
  return newNode;
}

// More complex insertion, deletion operations omitted for brevity

  

The B Tree example shows a simple node creation structure. In a B Tree, each node can contain multiple keys and have several children, balancing the tree during insertions and deletions to maintain the minimum and maximum keys.

B+ Tree

A B+ Tree is an extension of the B Tree. It stores all values at the leaf level and maintains a linked list of leaf nodes to provide efficient range queries. Internal nodes only store keys and act as guides to the leaf nodes.

// Example: Simple B+ Tree Leaf Node Concept
struct BPlusTreeNode {
  int data[MAX + 1];
  struct BPlusTreeNode* nextLeaf; // Linked list connection for range search
  struct BPlusTreeNode* children[MAX + 1];
  int isLeaf;
};

// Leaf and internal node handling omitted for brevity

  

The B+ Tree structure keeps data at the leaves with linked lists, making range searches very efficient. Internal nodes only guide the searches, optimizing search, insertion, and deletion operations in databases.

Red-Black Tree

A Red-Black Tree is a self-balancing binary search tree that ensures the tree remains balanced with simple rules during insertion and deletion. Each node is colored red or black, and certain properties are maintained to balance the tree.

// Example: Red-Black Tree Node Structure in C
enum Color { RED, BLACK };

struct RBTreeNode {
  int data;
  enum Color color;
  struct RBTreeNode* left, *right, *parent;
};

// Insert, delete, and balancing operations omitted for brevity

  

In a Red-Black Tree, operations are governed by rules related to the coloring of nodes (red/black), which ensure that the tree remains approximately balanced, allowing operations to be performed in O(log n) time.

Graphs

Graph Implementation

A Graph is a data structure consisting of a set of nodes (vertices) and edges (connections between nodes). It can be represented in various ways, such as an Adjacency Matrix or an Adjacency List.

// Example: Graph Implementation using Adjacency List in C
#include 
#include 

// Structure to represent a node in the adjacency list
struct Node {
  int vertex;
  struct Node* next;
};

// Structure to represent a graph
struct Graph {
  int numVertices;
  struct Node** adjLists;
};

// Create a new node
struct Node* createNode(int vertex) {
  struct Node* newNode = malloc(sizeof(struct Node));
  newNode->vertex = vertex;
  newNode->next = NULL;
  return newNode;
}

// Create a graph with n vertices
struct Graph* createGraph(int vertices) {
  struct Graph* graph = malloc(sizeof(struct Graph));
  graph->numVertices = vertices;

  // Initialize each adjacency list
  graph->adjLists = malloc(vertices * sizeof(struct Node*));
  for (int i = 0; i < vertices; i++)
    graph->adjLists[i] = NULL;

  return graph;
}

// Add edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest) {
  struct Node* newNode = createNode(dest);
  newNode->next = graph->adjLists[src];
  graph->adjLists[src] = newNode;

  // Add edge for the opposite direction (since undirected)
  newNode = createNode(src);
  newNode->next = graph->adjLists[dest];
  graph->adjLists[dest] = newNode;
}

  

This example demonstrates a graph implementation using an Adjacency List. The Graph structure holds a list of nodes for each vertex. The addEdge function adds edges in both directions for an undirected graph.

BFS (Breadth-First Search) Algorithm

The Breadth-First Search (BFS) algorithm traverses a graph level by level. It starts from a given node and explores all its neighbors before moving on to the next level. A queue data structure is typically used to keep track of the nodes to be visited.

// Example: BFS Algorithm in C
#include 
#include 

#define SIZE 40

struct Graph {
  int numVertices;
  int adjMatrix[SIZE][SIZE];
  int visited[SIZE];
};

// Function to perform BFS
void bfs(struct Graph* graph, int startVertex) {
  int queue[SIZE], front = 0, rear = 0;
  graph->visited[startVertex] = 1;
  queue[rear++] = startVertex;

  while (front != rear) {
    int currentVertex = queue[front++];
    printf("%d ", currentVertex);

    for (int i = 0; i < graph->numVertices; i++) {
      if (graph->adjMatrix[currentVertex][i] == 1 && !graph->visited[i]) {
        queue[rear++] = i;
        graph->visited[i] = 1;
      }
    }
  }
}

  

The BFS code snippet uses a queue to explore the graph. It marks nodes as visited when they are added to the queue to avoid revisiting them. This method ensures that all nodes at the current level are visited before moving deeper.

DFS (Depth-First Search) Algorithm

The Depth-First Search (DFS) algorithm explores a graph by going as deep as possible down one path before backtracking. It uses a stack (or recursion) to keep track of the current path and visited nodes.

// Example: DFS Algorithm in C
#include 
#include 

#define SIZE 40

struct Graph {
  int numVertices;
  int adjMatrix[SIZE][SIZE];
  int visited[SIZE];
};

// Function to perform DFS
void dfs(struct Graph* graph, int vertex) {
  graph->visited[vertex] = 1;
  printf("%d ", vertex);

  for (int i = 0; i < graph->numVertices; i++) {
    if (graph->adjMatrix[vertex][i] == 1 && !graph->visited[i]) {
      dfs(graph, i);
    }
  }
}

  

The DFS code example relies on recursion to traverse the graph. The visited array tracks which nodes have been explored to avoid cycles. DFS is ideal for tasks like finding connected components in a graph.

What is a Spanning Tree?

A Spanning Tree is a subgraph of a connected, undirected graph that includes all the vertices with the minimum possible number of edges. A Minimum Spanning Tree (MST) is a spanning tree where the sum of the edge weights is minimized.

There are two main algorithms to find the Minimum Spanning Tree of a graph: Prim's Algorithm and Kruskal's Algorithm. Each has its own approach to building the MST.

Prim's Algorithm

Prim's Algorithm builds the Minimum Spanning Tree by starting with an arbitrary node and growing the MST one edge at a time. It repeatedly adds the smallest edge that connects a vertex in the MST to a vertex outside the MST.

// Example: Prim's Algorithm in C
#include 
#include 
#define V 5

int minKey(int key[], int mstSet[]) {
  int min = INT_MAX, min_index;
  for (int v = 0; v < V; v++)
    if (mstSet[v] == 0 && key[v] < min) {
      min = key[v];
      min_index = v;
    }
  return min_index;
}

void printMST(int parent[], int graph[V][V]) {
  printf("Edge \tWeight\\n");
  for (int i = 1; i < V; i++)
    printf("%d - %d \t%d\\n", parent[i], i, graph[i][parent[i]]);
}

void primMST(int graph[V][V]) {
  int parent[V];
  int key[V];
  int mstSet[V];

  for (int i = 0; i < V; i++) {
    key[i] = INT_MAX;
    mstSet[i] = 0;
  }

  key[0] = 0;
  parent[0] = -1;

  for (int count = 0; count < V - 1; count++) {
    int u = minKey(key, mstSet);
    mstSet[u] = 1;

    for (int v = 0; v < V; v++)
      if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v]) {
        parent[v] = u;
        key[v] = graph[u][v];
      }
  }

  printMST(parent, graph);
}

int main() {
  int graph[V][V] = {
    {0, 2, 0, 6, 0},
    {2, 0, 3, 8, 5},
    {0, 3, 0, 0, 7},
    {6, 8, 0, 0, 9},
    {0, 5, 7, 9, 0}
  };

  primMST(graph);

  return 0;
}

  

In this example, Prim's Algorithm is implemented using an adjacency matrix. The function minKey selects the next minimum key value that isn't included in the MST. The algorithm builds the MST step-by-step by adding the smallest edge at each iteration.

Kruskal's Algorithm

Kruskal's Algorithm builds the Minimum Spanning Tree by sorting all the edges by weight and repeatedly adding the smallest edge, ensuring that no cycles are formed. It uses the Union-Find (or Disjoint Set) data structure to manage connected components.

// Example: Kruskal's Algorithm in C
#include 
#include 

#define V 5

struct Edge {
  int src, dest, weight;
};

struct Graph {
  int V, E;
  struct Edge* edges;
};

struct Graph* createGraph(int V, int E) {
  struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
  graph->V = V;
  graph->E = E;
  graph->edges = (struct Edge*)malloc(E * sizeof(struct Edge));
  return graph;
}

struct Subset {
  int parent;
  int rank;
};

int find(struct Subset subsets[], int i) {
  if (subsets[i].parent != i)
    subsets[i].parent = find(subsets, subsets[i].parent);
  return subsets[i].parent;
}

void Union(struct Subset subsets[], int x, int y) {
  int rootX = find(subsets, x);
  int rootY = find(subsets, y);

  if (subsets[rootX].rank < subsets[rootY].rank)
    subsets[rootX].parent = rootY;
  else if (subsets[rootX].rank > subsets[rootY].rank)
    subsets[rootY].parent = rootX;
  else {
    subsets[rootY].parent = rootX;
    subsets[rootX].rank++;
  }
}

int compareEdges(const void* a, const void* b) {
  struct Edge* edgeA = (struct Edge*)a;
  struct Edge* edgeB = (struct Edge*)b;
  return edgeA->weight > edgeB->weight;
}

void KruskalMST(struct Graph* graph) {
  int V = graph->V;
  struct Edge result[V];
  int e = 0, i = 0;

  qsort(graph->edges, graph->E, sizeof(graph->edges[0]), compareEdges);

  struct Subset* subsets = (struct Subset*)malloc(V * sizeof(struct Subset));
  for (int v = 0; v < V; ++v) {
    subsets[v].parent = v;
    subsets[v].rank = 0;
  }

  while (e < V - 1 && i < graph->E) {
    struct Edge nextEdge = graph->edges[i++];

    int x = find(subsets, nextEdge.src);
    int y = find(subsets, nextEdge.dest);

    if (x != y) {
      result[e++] = nextEdge;
      Union(subsets, x, y);
    }
  }

  printf("Edge \tWeight\\n");
  for (i = 0; i < e; ++i)
    printf("%d - %d \t%d\\n", result[i].src, result[i].dest, result[i].weight);
}

int main() {
  int V = 5;
  int E = 7;
  struct Graph* graph = createGraph(V, E);

  graph->edges[0] = (struct Edge){0, 1, 2};
  graph->edges[1] = (struct Edge){0, 3, 6};
  graph->edges[2] = (struct Edge){1, 2, 3};
  graph->edges[3] = (struct Edge){1, 3, 8};
  graph->edges[4] = (struct Edge){1, 4, 5};
  graph->edges[5] = (struct Edge){2, 4, 7};
  graph->edges[6] = (struct Edge){3, 4, 9};

  KruskalMST(graph);

  return 0;
}

  

Kruskal's Algorithm is demonstrated here using the Union-Find data structure to keep track of connected components. The graph's edges are sorted by weight, and the smallest edges are added to the MST until all vertices are connected.

Searching

Introduction to Searching

In data structures, searching is the process of finding a particular element within a data set. Efficient searching algorithms are crucial for optimizing performance in applications involving large datasets. Two fundamental searching techniques are Linear Search and Binary Search.

Linear Search

Linear Search is the simplest searching algorithm. It sequentially checks each element in the list until the desired element is found or the list ends. Linear Search is best used when the data is unsorted, as it does not rely on any specific order.

// Example: Linear Search in C
#include 

int linearSearch(int arr[], int size, int target) {
  for (int i = 0; i < size; i++) {
    if (arr[i] == target) {
      return i;  // Target found at index i
    }
  }
  return -1;  // Target not found
}

int main() {
  int arr[] = {5, 2, 9, 1, 6, 8};
  int size = sizeof(arr) / sizeof(arr[0]);
  int target = 6;

  int result = linearSearch(arr, size, target);
  if (result != -1)
    printf("Element found at index: %d\\n", result);
  else
    printf("Element not found\\n");

  return 0;
}

  

In this Linear Search example, each element in the array is compared to the target value. If the target is found, the index is returned; otherwise, the function returns -1 indicating that the target is not present.

Time Complexity: O(n), where n is the number of elements. This is because each element might have to be checked in the worst case.

Binary Search

Binary Search is a more efficient searching technique that requires the data to be sorted. It works by repeatedly dividing the search interval in half. If the target value is less than the middle element, the search continues in the left half, otherwise in the right half.

// Example: Binary Search in C
#include 

int binarySearch(int arr[], int low, int high, int target) {
  while (low <= high) {
    int mid = low + (high - low) / 2;

    if (arr[mid] == target) {
      return mid;  // Target found at index mid
    }
    if (arr[mid] < target) {
      low = mid + 1;  // Continue in the right half
    } else {
      high = mid - 1;  // Continue in the left half
    }
  }
  return -1;  // Target not found
}

int main() {
  int arr[] = {1, 2, 5, 6, 8, 9};
  int size = sizeof(arr) / sizeof(arr[0]);
  int target = 6;

  int result = binarySearch(arr, 0, size - 1, target);
  if (result != -1)
    printf("Element found at index: %d\\n", result);
  else
    printf("Element not found\\n");

  return 0;
}

  

In this Binary Search example, the function iteratively divides the sorted array and searches for the target value in the appropriate half. This significantly reduces the number of comparisons needed.

Time Complexity: O(log n), where n is the number of elements. This is due to the halving of the search space with each iteration, making Binary Search much faster than Linear Search for sorted data.

Sorting

Introduction to Sorting

Sorting is the process of arranging data in a particular order (either ascending or descending). Efficient sorting algorithms are crucial for optimizing the performance of applications that process large amounts of data. In this section, we will explore three different sorting algorithms: Bubble Sort, Bucket Sort, and Comb Sort.

Bubble Sort

Bubble Sort is a simple comparison-based sorting algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until the list is sorted.

// Example: Bubble Sort in C
#include 

void bubbleSort(int arr[], int n) {
  for (int i = 0; i < n-1; i++) {
    for (int j = 0; j < n-i-1; j++) {
      if (arr[j] > arr[j+1]) {
        // Swap arr[j] and arr[j+1]
        int temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
}

int main() {
  int arr[] = {5, 2, 9, 1, 5, 6};
  int size = sizeof(arr) / sizeof(arr[0]);
  bubbleSort(arr, size);

  printf("Sorted array: ");
  for (int i = 0; i < size; i++) {
    printf("%d ", arr[i]);
  }
  return 0;
}

  

Bubble Sort works by repeatedly swapping adjacent elements that are out of order. Although easy to implement, it has a poor average and worst-case performance.

Time Complexity: O(n²) in the worst and average case. Bubble Sort is rarely used in practice for large datasets due to its inefficiency.

Bucket Sort

Bucket Sort distributes elements into several buckets, sorts each bucket individually (using another sorting algorithm like Insertion Sort), and then combines the sorted buckets. It is particularly effective when the input is uniformly distributed over a range.

// Example: Bucket Sort in C
#include 
#include 

#define BUCKETS 10
#define MAX 10

void bucketSort(float arr[], int n) {
  // Create an array of buckets
  float buckets[BUCKETS][MAX] = {0};
  int bucketCount[BUCKETS] = {0};

  // Place array elements into buckets
  for (int i = 0; i < n; i++) {
    int idx = (int)(arr[i] * BUCKETS);
    buckets[idx][bucketCount[idx]++] = arr[i];
  }

  // Sort individual buckets using Insertion Sort
  for (int i = 0; i < BUCKETS; i++) {
    for (int j = 1; j < bucketCount[i]; j++) {
      float key = buckets[i][j];
      int k = j - 1;
      while (k >= 0 && buckets[i][k] > key) {
        buckets[i][k + 1] = buckets[i][k];
        k--;
      }
      buckets[i][k + 1] = key;
    }
  }

  // Concatenate all buckets into the original array
  int index = 0;
  for (int i = 0; i < BUCKETS; i++) {
    for (int j = 0; j < bucketCount[i]; j++) {
      arr[index++] = buckets[i][j];
    }
  }
}

int main() {
  float arr[] = {0.42, 0.32, 0.53, 0.27, 0.68, 0.22, 0.45, 0.76, 0.89};
  int size = sizeof(arr) / sizeof(arr[0]);
  bucketSort(arr, size);

  printf("Sorted array: ");
  for (int i = 0; i < size; i++) {
    printf("%.2f ", arr[i]);
  }
  return 0;
}

  

Bucket Sort can be very efficient if the data is uniformly distributed. However, it requires careful selection of the bucket range to be effective.

Time Complexity: O(n + k), where n is the number of elements and k is the number of buckets. It can approach O(n) time if the elements are evenly distributed among the buckets.

Comb Sort

Comb Sort is an improvement over Bubble Sort. It eliminates small values near the end of the list that slow down Bubble Sort. It does this by comparing elements with a gap larger than one and gradually reducing the gap size until it reaches one.

// Example: Comb Sort in C
#include 

int getNextGap(int gap) {
  // Shrink factor 1.3
  gap = (gap * 10) / 13;
  if (gap < 1)
    return 1;
  return gap;
}

void combSort(int arr[], int n) {
  int gap = n;
  int swapped = 1;

  while (gap != 1 || swapped) {
    gap = getNextGap(gap);
    swapped = 0;

    for (int i = 0; i < n - gap; i++) {
      if (arr[i] > arr[i + gap]) {
        // Swap arr[i] and arr[i + gap]
        int temp = arr[i];
        arr[i] = arr[i + gap];
        arr[i + gap] = temp;
        swapped = 1;
      }
    }
  }
}

int main() {
  int arr[] = {8, 4, 1, 56, 3, -44, 23, -6, 28, 0};
  int size = sizeof(arr) / sizeof(arr[0]);
  combSort(arr, size);

  printf("Sorted array: ");
  for (int i = 0; i < size; i++) {
    printf("%d ", arr[i]);
  }
  return 0;
}

  

Comb Sort enhances Bubble Sort by using a gap to reduce the number of swaps needed. As the gap reduces to one, it behaves similarly to Bubble Sort.

Time Complexity: O(n²) in the worst case, but it generally performs better than Bubble Sort due to the gap reduction.

Counting Sort

Counting Sort is a non-comparison-based sorting algorithm. It works by counting the number of occurrences of each unique element, using those counts to determine the position of each element in the final sorted array. It is effective when the range of potential items is not significantly greater than the number of items.

// Example: Counting Sort in C
#include 
#include 

void countingSort(int arr[], int size, int max) {
  int count[max + 1];
  int output[size];

  // Initialize count array to 0
  memset(count, 0, sizeof(count));

  // Count occurrences of each number
  for (int i = 0; i < size; i++) {
    count[arr[i]]++;
  }

  // Update count to contain positions of numbers
  for (int i = 1; i <= max; i++) {
    count[i] += count[i - 1];
  }

  // Build the output array
  for (int i = size - 1; i >= 0; i--) {
    output[count[arr[i]] - 1] = arr[i];
    count[arr[i]]--;
  }

  // Copy sorted elements back to the original array
  for (int i = 0; i < size; i++) {
    arr[i] = output[i];
  }
}

int main() {
  int arr[] = {4, 2, 2, 8, 3, 3, 1};
  int size = sizeof(arr) / sizeof(arr[0]);
  int max = 8; // Maximum value in the array
  countingSort(arr, size, max);

  printf("Sorted array: ");
  for (int i = 0; i < size; i++) {
    printf("%d ", arr[i]);
  }
  return 0;
}

  

Counting Sort is efficient with small ranges of integers, but can be memory-intensive if the range is large.

Time Complexity: O(n + k), where n is the number of elements and k is the range of input.

Heap Sort

Heap Sort is a comparison-based sorting algorithm that uses a Binary Heap data structure. It sorts an array by building a max-heap and repeatedly extracting the maximum element to place it at the end of the array.

// Example: Heap Sort in C
#include 

// Function to heapify a subtree
void heapify(int arr[], int n, int i) {
  int largest = i;
  int left = 2 * i + 1;
  int right = 2 * i + 2;

  if (left < n && arr[left] > arr[largest])
    largest = left;

  if (right < n && arr[right] > arr[largest])
    largest = right;

  if (largest != i) {
    int temp = arr[i];
    arr[i] = arr[largest];
    arr[largest] = temp;

    heapify(arr, n, largest);
  }
}

void heapSort(int arr[], int n) {
  for (int i = n / 2 - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  for (int i = n - 1; i >= 0; i--) {
    int temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;

    heapify(arr, i, 0);
  }
}

int main() {
  int arr[] = {12, 11, 13, 5, 6, 7};
  int size = sizeof(arr) / sizeof(arr[0]);
  heapSort(arr, size);

  printf("Sorted array: ");
  for (int i = 0; i < size; i++) {
    printf("%d ", arr[i]);
  }
  return 0;
}

  

Heap Sort is in-place and efficient, making it suitable for large datasets.

Time Complexity: O(n log n) for both average and worst cases.

Insertion Sort

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much like sorting playing cards in your hands, where you take one card at a time and place it in its correct position.

    
      // Example: Insertion Sort in C
      #include 

      void insertionSort(int arr[], int n) {
        for (int i = 1; i < n; i++) {
          int key = arr[i];
          int j = i - 1;

          while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
          }
          arr[j + 1] = key;
        }
      }

      int main() {
        int arr[] = {12, 11, 13, 5, 6};
        int size = sizeof(arr) / sizeof(arr[0]);
        insertionSort(arr, size);

        printf("Sorted array: ");
        for (int i = 0; i < size; i++) {
          printf("%d ", arr[i]);
        }
        return 0;
      }
    
  

Insertion Sort is efficient for small datasets and nearly sorted arrays.

Time Complexity: O(n²) in the worst case, but O(n) for nearly sorted data.

Merge Sort

Merge Sort is a divide-and-conquer algorithm that splits the array into halves, sorts them, and merges the sorted halves. It is a stable sorting algorithm, which means it maintains the relative order of equal elements.

    
      // Example: Merge Sort in C
      #include 

      void merge(int arr[], int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int L[n1], R[n2];

        for (int i = 0; i < n1; i++)
          L[i] = arr[left + i];
        for (int j = 0; j < n2; j++)
          R[j] = arr[mid + 1 + j];

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
          if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
          } else {
            arr[k] = R[j];
            j++;
          }
          k++;
        }

        while (i < n1) {
          arr[k] = L[i];
          i++;
          k++;
        }

        while (j < n2) {
          arr[k] = R[j];
          j++;
          k++;
        }
      }

      void mergeSort(int arr[], int left, int right) {
        if (left < right) {
          int mid = left + (right - left) / 2;

          mergeSort(arr, left, mid);
          mergeSort(arr, mid + 1, right);
          merge(arr, left, mid, right);
        }
      }

      int main() {
        int arr[] = {12, 11, 13, 5, 6, 7};
        int size = sizeof(arr) / sizeof(arr[0]);
        mergeSort(arr, 0, size - 1);

        printf("Sorted array: ");
        for (int i = 0; i < size; i++) {
          printf("%d ", arr[i]);
        }
        return 0;
      }
    
  

Merge Sort is highly efficient for large datasets and guarantees O(n log n) complexity.

Time Complexity: O(n log n) for all cases.

Quick Sort

Quick Sort is a divide-and-conquer sorting algorithm. It works by selecting a 'pivot' element, partitioning the array into two parts — one containing elements less than the pivot and the other containing elements greater than the pivot. The process is recursively repeated for each partition.

    
      // Example: Quick Sort in C
      #include 

      void swap(int *x, int *y) {
          int temp = *x;
          *x = *y;
          *y = temp;
      }

      int partition(int arr[], int low, int high) {
          int pivot = arr[high];
          int i = (low - 1);

          for (int j = low; j < high; j++) {
              if (arr[j] < pivot) {
                  i++;
                  swap(&arr[i], &arr[j]);
              }
          }
          swap(&arr[i + 1], &arr[high]);
          return (i + 1);
      }

      void quickSort(int arr[], int low, int high) {
          if (low < high) {
              int pi = partition(arr, low, high);

              quickSort(arr, low, pi - 1);
              quickSort(arr, pi + 1, high);
          }
      }

      int main() {
          int arr[] = {10, 7, 8, 9, 1, 5};
          int n = sizeof(arr) / sizeof(arr[0]);
          quickSort(arr, 0, n - 1);

          printf("Sorted array: ");
          for (int i = 0; i < n; i++) {
              printf("%d ", arr[i]);
          }
          return 0;
      }
    
  

Quick Sort is one of the fastest sorting algorithms for large datasets. Its average-case time complexity is O(n log n), but in the worst case, it can degrade to O(n²).

Time Complexity: O(n log n) on average, O(n²) in the worst case.

Radix Sort

Radix Sort is a non-comparative sorting algorithm that sorts numbers by processing individual digits. It processes the digits from the least significant to the most significant or vice versa. Radix Sort is effective for sorting large numbers and integers with a known range.

    
      // Example: Radix Sort in C
      #include 
      #include 

      int getMax(int arr[], int n) {
          int max = arr[0];
          for (int i = 1; i < n; i++) {
              if (arr[i] > max) {
                  max = arr[i];
              }
          }
          return max;
      }

      void countSort(int arr[], int n, int exp) {
          int output[n];
          int count[10] = {0};

          for (int i = 0; i < n; i++) {
              count[(arr[i] / exp) % 10]++;
          }

          for (int i = 1; i < 10; i++) {
              count[i] += count[i - 1];
          }

          for (int i = n - 1; i >= 0; i--) {
              output[count[(arr[i] / exp) % 10] - 1] = arr[i];
              count[(arr[i] / exp) % 10]--;
          }

          for (int i = 0; i < n; i++) {
              arr[i] = output[i];
          }
      }

      void radixSort(int arr[], int n) {
          int max = getMax(arr, n);

          for (int exp = 1; max / exp > 0; exp *= 10) {
              countSort(arr, n, exp);
          }
      }

      int main() {
          int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
          int n = sizeof(arr) / sizeof(arr[0]);
          radixSort(arr, n);

          printf("Sorted array: ");
          for (int i = 0; i < n; i++) {
              printf("%d ", arr[i]);
          }
          return 0;
      }
    
  

Radix Sort works well when sorting large datasets with small integer values or fixed-length strings.

Time Complexity: O(nk), where `n` is the number of elements and `k` is the number of digits.

Selection Sort

Selection Sort is a simple comparison-based sorting algorithm. It repeatedly selects the smallest element from the unsorted portion of the array and swaps it with the first unsorted element. It is not efficient on large lists.

    
      // Example: Selection Sort in C
      #include 

      void selectionSort(int arr[], int n) {
          for (int i = 0; i < n - 1; i++) {
              int minIndex = i;
              for (int j = i + 1; j < n; j++) {
                  if (arr[j] < arr[minIndex]) {
                      minIndex = j;
                  }
              }
              int temp = arr[minIndex];
              arr[minIndex] = arr[i];
              arr[i] = temp;
          }
      }

      int main() {
          int arr[] = {64, 25, 12, 22, 11};
          int n = sizeof(arr) / sizeof(arr[0]);
          selectionSort(arr, n);

          printf("Sorted array: ");
          for (int i = 0; i < n; i++) {
              printf("%d ", arr[i]);
          }
          return 0;
      }
    
  

Selection Sort is easy to implement but inefficient for large datasets. It always performs O(n²) comparisons.

Time Complexity: O(n²) for all cases.

Shell Sort

Shell Sort is an optimization of Insertion Sort. It allows the exchange of items that are far apart, making the algorithm faster than traditional insertion sort for larger datasets. It uses a gap sequence to break the list into sublists and performs insertion sort on each sublist.

    
      // Example: Shell Sort in C
      #include 

      void shellSort(int arr[], int n) {
          for (int gap = n / 2; gap > 0; gap /= 2) {
              for (int i = gap; i < n; i++) {
                  int temp = arr[i];
                  int j = i;

                  while (j >= gap && arr[j - gap] > temp) {
                      arr[j] = arr[j - gap];
                      j -= gap;
                  }
                  arr[j] = temp;
              }
          }
      }

      int main() {
          int arr[] = {12, 34, 54, 2, 3};
          int n = sizeof(arr) / sizeof(arr[0]);
          shellSort(arr, n);

          printf("Sorted array: ");
          for (int i = 0; i < n; i++) {
              printf("%d ", arr[i]);
          }
          return 0;
      }
    
  

Shell Sort improves on Insertion Sort by using a gap sequence, which reduces the number of swaps needed for sorting.

Time Complexity: O(n log n) in the best case, but can be O(n²) depending on the gap sequence.

Bitonic Sort

Bitonic Sort is a parallel sorting algorithm based on the concept of bitonic sequences. A bitonic sequence is a sequence of numbers that first increases and then decreases, or vice versa. The algorithm works by recursively sorting and merging the sequence into bitonic subsequences.

    
      // Example: Bitonic Sort in C
      #include 

      void swap(int *x, int *y) {
          int temp = *x;
          *x = *y;
          *y = temp;
      }

      void bitonicMerge(int arr[], int low, int cnt, int dir) {
          if (cnt > 1) {
              int k = cnt / 2;
              for (int i = low; i < low + k; i++) {
                  if ((arr[i] > arr[i + k]) == dir) {
                      swap(&arr[i], &arr[i + k]);
                  }
              }
              bitonicMerge(arr, low, k, dir);
              bitonicMerge(arr, low + k, k, dir);
          }
      }

      void bitonicSort(int arr[], int low, int cnt, int dir) {
          if (cnt > 1) {
              int k = cnt / 2;
              bitonicSort(arr, low, k, 1); // Ascending order
              bitonicSort(arr, low + k, k, 0); // Descending order
              bitonicMerge(arr, low, cnt, dir);
          }
      }

      int main() {
          int arr[] = {3, 7, 2, 1, 8, 5, 4, 6};
          int n = sizeof(arr) / sizeof(arr[0]);
          bitonicSort(arr, 0, n, 1);

          printf("Sorted array: ");
          for (int i = 0; i < n; i++) {
              printf("%d ", arr[i]);
          }
          return 0;
      }
    
  

Bitonic Sort is efficient on parallel hardware, but it is not practical for serial processing. It is commonly used in parallel computing systems.

Time Complexity: O(n log² n)

Cocktail Sort

Cocktail Sort is a variation of Bubble Sort. It sorts in both directions on each pass through the list, moving from left to right and then from right to left. This allows Cocktail Sort to potentially sort more efficiently than Bubble Sort in some cases.

    
      // Example: Cocktail Sort in C
      #include 

      void cocktailSort(int arr[], int n) {
          int swapped = 1;
          int start = 0;
          int end = n - 1;

          while (swapped) {
              swapped = 0;

              for (int i = start; i < end; i++) {
                  if (arr[i] > arr[i + 1]) {
                      int temp = arr[i];
                      arr[i] = arr[i + 1];
                      arr[i + 1] = temp;
                      swapped = 1;
                  }
              }

              if (!swapped) break;

              swapped = 0;
              end--;

              for (int i = end - 1; i >= start; i--) {
                  if (arr[i] > arr[i + 1]) {
                      int temp = arr[i];
                      arr[i] = arr[i + 1];
                      arr[i + 1] = temp;
                      swapped = 1;
                  }
              }
              start++;
          }
      }

      int main() {
          int arr[] = {5, 3, 8, 4, 2};
          int n = sizeof(arr) / sizeof(arr[0]);
          cocktailSort(arr, n);

          printf("Sorted array: ");
          for (int i = 0; i < n; i++) {
              printf("%d ", arr[i]);
          }
          return 0;
      }
    
  

Cocktail Sort is more efficient than Bubble Sort in cases where elements are located near their final positions, as it sorts in both directions.

Time Complexity: O(n²)

Cycle Sort

Cycle Sort is an in-place, non-comparative sorting algorithm. It works by finding the cycle in the list and rotating it to sort the elements. Cycle Sort minimizes the number of writes to the array, making it ideal for situations where the cost of writing is high.

    
      // Example: Cycle Sort in C
      #include 

      void cycleSort(int arr[], int n) {
          for (int cycleStart = 0; cycleStart <= n - 2; cycleStart++) {
              int item = arr[cycleStart];
              int pos = cycleStart;

              for (int i = cycleStart + 1; i < n; i++) {
                  if (arr[i] < item) {
                      pos++;
                  }
              }

              if (pos == cycleStart) continue;

              while (item == arr[pos]) {
                  pos++;
              }

              int temp = arr[pos];
              arr[pos] = item;
              item = temp;

              while (pos != cycleStart) {
                  pos = cycleStart;
                  for (int i = cycleStart + 1; i < n; i++) {
                      if (arr[i] < item) {
                          pos++;
                      }
                  }

                  while (item == arr[pos]) {
                      pos++;
                  }

                  temp = arr[pos];
                  arr[pos] = item;
                  item = temp;
              }
          }
      }

      int main() {
          int arr[] = {5, 2, 9, 1, 5, 6};
          int n = sizeof(arr) / sizeof(arr[0]);
          cycleSort(arr, n);

          printf("Sorted array: ");
          for (int i = 0; i < n; i++) {
              printf("%d ", arr[i]);
          }
          return 0;
      }
    
  

Cycle Sort is especially useful when memory writes are costly, as it minimizes the number of writes required during the sorting process.

Time Complexity: O(n²)

Tim Sort

Tim Sort is a hybrid sorting algorithm derived from Merge Sort and Insertion Sort. It is optimized for real-world data and is used in Python's built-in sort() function and Java’s Arrays.sort(). Tim Sort works by dividing the array into smaller segments, sorting each segment with Insertion Sort, and then merging the sorted segments with Merge Sort.

    
      // Example: Tim Sort (conceptual code)
      #include 

      void insertionSort(int arr[], int left, int right) {
          for (int i = left + 1; i <= right; i++) {
              int temp = arr[i];
              int j = i - 1;
              while (j >= left && arr[j] > temp) {
                  arr[j + 1] = arr[j];
                  j--;
              }
              arr[j + 1] = temp;
          }
      }

      void merge(int arr[], int left, int right, int mid) {
          int n1 = mid - left + 1;
          int n2 = right - mid;

          int leftArr[n1], rightArr[n2];

          for (int i = 0; i < n1; i++) {
              leftArr[i] = arr[left + i];
          }
          for (int j = 0; j < n2; j++) {
              rightArr[j] = arr[mid + 1 + j];
          }

          int i = 0, j = 0, k = left;
          while (i < n1 && j < n2) {
              if (leftArr[i] <= rightArr[j]) {
                  arr[k] = leftArr[i];
                  i++;
              } else {
                  arr[k] = rightArr[j];
                  j++;
              }
              k++;
          }

          while (i < n1) {
              arr[k] = leftArr[i];
              i++;
              k++;
          }

          while (j < n2) {
              arr[k] = rightArr[j];
              j++;
              k++;
          }
      }

      void timSort(int arr[], int n) {
          const int RUN = 32;
          for (int i = 0; i < n; i += RUN) {
              insertionSort(arr, i, std::min((i + RUN - 1), (n - 1)));
          }

          for (int size = RUN; size < n; size = 2 * size) {
              for (int left = 0; left < n; left += 2 * size) {
                  int mid = std::min(n - 1, left + size - 1);
                  int right = std::min((left + 2 * size - 1), (n - 1));
                  if (mid < right) {
                      merge(arr, left, right, mid);
                  }
              }
          }
      }

      int main() {
          int arr[] = {5, 2, 9, 1, 5, 6};
          int n = sizeof(arr) / sizeof(arr[0]);
          timSort(arr, n);

          printf("Sorted array: ");
          for (int i = 0; i < n; i++) {
              printf("%d ", arr[i]);
          }
          return 0;
      }
    
  

Tim Sort is highly efficient for practical use, making it a go-to algorithm in production systems for sorting.

Time Complexity: O(n log n) in the worst case

Singly Linked List

Singly Linked List

A Singly Linked List is a linear data structure where each element is a node containing data and a reference to the next node in the sequence. It allows efficient insertion and deletion from the beginning of the list, but accessing elements in the middle or end is less efficient.

Insertion at Beginning

Inserting a node at the beginning of the list involves creating a new node and pointing its next reference to the current head of the list. The new node becomes the new head.

    
      // Example: Singly Linked List - Insertion at Beginning in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* next;
      };

      // Function to insert a node at the beginning
      void insertAtBeginning(struct Node** head, int newData) {
          // Allocate new node
          struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
          
          // Assign data to the new node
          newNode->data = newData;

          // Point next of the new node to the current head
          newNode->next = *head;

          // Move head to point to the new node
          *head = newNode;
      }

      // Function to print the list
      void printList(struct Node* head) {
          struct Node* temp = head;
          while (temp != NULL) {
              printf("%d -> ", temp->data);
              temp = temp->next;
          }
          printf("NULL\n");
      }

      int main() {
          struct Node* head = NULL;
          
          // Inserting nodes at the beginning
          insertAtBeginning(&head, 10);
          insertAtBeginning(&head, 20);
          insertAtBeginning(&head, 30);

          // Printing the list
          printf("Linked List: ");
          printList(head);

          return 0;
      }
    
  

Explanation: The `insertAtBeginning` function creates a new node, sets its data, and points its `next` to the current head. The head pointer is updated to the new node.

Time Complexity: O(1) for insertion at the beginning.

Insertion at End

Inserting a node at the end of the list involves traversing the list until the last node and then attaching the new node at the end. This operation requires a traversal of the entire list.

    
      // Example: Singly Linked List - Insertion at End in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* next;
      };

      // Function to insert a node at the end
      void insertAtEnd(struct Node** head, int newData) {
          // Allocate new node
          struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
          struct Node* last = *head;

          // Assign data to the new node
          newNode->data = newData;
          newNode->next = NULL;

          // If the list is empty, make the new node as the head
          if (*head == NULL) {
              *head = newNode;
              return;
          }

          // Traverse to the last node
          while (last->next != NULL) {
              last = last->next;
          }

          // Point the last node's next to the new node
          last->next = newNode;
      }

      // Function to print the list
      void printList(struct Node* head) {
          struct Node* temp = head;
          while (temp != NULL) {
              printf("%d -> ", temp->data);
              temp = temp->next;
          }
          printf("NULL\n");
      }

      int main() {
          struct Node* head = NULL;
          
          // Inserting nodes at the end
          insertAtEnd(&head, 10);
          insertAtEnd(&head, 20);
          insertAtEnd(&head, 30);

          // Printing the list
          printf("Linked List: ");
          printList(head);

          return 0;
      }
    
  

Explanation: The `insertAtEnd` function allocates a new node, sets its data, and traverses the list until it finds the last node. The last node's `next` is updated to point to the new node.

Time Complexity: O(n) for insertion at the end (due to traversal).

Insertion After Specified Node

Inserting a node after a specified node involves traversing the list to find the target node, and then linking the new node after it.

    
      // Example: Singly Linked List - Insertion after Specified Node in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* next;
      };

      // Function to insert a new node after a given node
      void insertAfter(struct Node* prevNode, int newData) {
          // Check if the given node is NULL
          if (prevNode == NULL) {
              printf("Previous node cannot be NULL\n");
              return;
          }

          // Allocate new node
          struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

          // Assign data to the new node
          newNode->data = newData;

          // Make next of new node as next of previous node
          newNode->next = prevNode->next;

          // Move the next of the previous node to point to the new node
          prevNode->next = newNode;
      }

      // Function to print the list
      void printList(struct Node* head) {
          struct Node* temp = head;
          while (temp != NULL) {
              printf("%d -> ", temp->data);
              temp = temp->next;
          }
          printf("NULL\n");
      }

      int main() {
          struct Node* head = NULL;
          struct Node* second = NULL;
          struct Node* third = NULL;

          // Allocate memory for nodes
          head = (struct Node*)malloc(sizeof(struct Node));
          second = (struct Node*)malloc(sizeof(struct Node));
          third = (struct Node*)malloc(sizeof(struct Node));

          // Assign data to nodes
          head->data = 10;
          head->next = second;

          second->data = 20;
          second->next = third;

          third->data = 30;
          third->next = NULL;

          // Insert after second node
          insertAfter(second, 25);

          // Print the list
          printf("Linked List: ");
          printList(head);

          return 0;
      }
    
  

Explanation: The `insertAfter` function inserts a new node after the specified node (`prevNode`). It updates the `next` pointer of the previous node to point to the new node, and the new node points to the next node of `prevNode`.

Time Complexity: O(1), since we already have the reference to the specified node.

Deletion at Beginning

Deleting a node at the beginning involves updating the head pointer to point to the next node, effectively removing the first node from the list.

    
      // Example: Singly Linked List - Deletion at Beginning in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* next;
      };

      // Function to delete the first node
      void deleteAtBeginning(struct Node** head) {
          // Check if the list is empty
          if (*head == NULL) {
              printf("List is empty\n");
              return;
          }

          // Store the current head
          struct Node* temp = *head;

          // Move head to the next node
          *head = (*head)->next;

          // Free the memory of the old head
          free(temp);
      }

      // Function to print the list
      void printList(struct Node* head) {
          struct Node* temp = head;
          while (temp != NULL) {
              printf("%d -> ", temp->data);
              temp = temp->next;
          }
          printf("NULL\n");
      }

      int main() {
          struct Node* head = NULL;

          // Allocate memory for nodes
          head = (struct Node*)malloc(sizeof(struct Node));

          head->data = 10;
          head->next = NULL;

          // Deleting the first node
          deleteAtBeginning(&head);

          // Print the list
          printf("Linked List: ");
          printList(head);

          return 0;
      }
    
  

Explanation: The `deleteAtBeginning` function removes the first node by updating the head pointer to the next node and freeing the memory of the old head.

Time Complexity: O(1), as we directly access the head node.

Deletion at End

Deleting a node at the end requires traversing the list to find the second last node and updating its `next` pointer to `NULL`, then freeing the memory of the last node.

    
      // Example: Singly Linked List - Deletion at End in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* next;
      };

      // Function to delete the last node
      void deleteAtEnd(struct Node** head) {
          // Check if the list is empty
          if (*head == NULL) {
              printf("List is empty\n");
              return;
          }

          // If the list contains only one node
          if ((*head)->next == NULL) {
              free(*head);
              *head = NULL;
              return;
          }

          // Traverse to the second last node
          struct Node* temp = *head;
          while (temp->next != NULL && temp->next->next != NULL) {
              temp = temp->next;
          }

          // Free the memory of the last node
          free(temp->next);

          // Set the second last node's next to NULL
          temp->next = NULL;
      }

      // Function to print the list
      void printList(struct Node* head) {
          struct Node* temp = head;
          while (temp != NULL) {
              printf("%d -> ", temp->data);
              temp = temp->next;
          }
          printf("NULL\n");
      }

      int main() {
          struct Node* head = NULL;
          struct Node* second = NULL;
          struct Node* third = NULL;

          // Allocate memory for nodes
          head = (struct Node*)malloc(sizeof(struct Node));
          second = (struct Node*)malloc(sizeof(struct Node));
          third = (struct Node*)malloc(sizeof(struct Node));

          // Assign data to nodes
          head->data = 10;
          head->next = second;

          second->data = 20;
          second->next = third;

          third->data = 30;
          third->next = NULL;

          // Deleting the last node
          deleteAtEnd(&head);

          // Print the list
          printf("Linked List: ");
          printList(head);

          return 0;
      }
    
  

Explanation: The `deleteAtEnd` function traverses the list to find the second last node, then updates its `next` pointer to `NULL` and frees the last node.

Time Complexity: O(n) for deletion at the end (due to traversal).

Deletion After Specified Node

Deleting a node after a specified node involves checking that the next node is not NULL, and then updating the `next` pointer of the specified node to skip the node to be deleted.

    
      // Example: Singly Linked List - Deletion after Specified Node in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* next;
      };

      // Function to delete a node after a given node
      void deleteAfter(struct Node* prevNode) {
          // Check if the previous node or its next node is NULL
          if (prevNode == NULL || prevNode->next == NULL) {
              printf("Cannot delete after this node\n");
              return;
          }

          // Store the node to be deleted
          struct Node* temp = prevNode->next;

          // Change the next of previous node to skip the node to be deleted
          prevNode->next = temp->next;

          // Free memory of the deleted node
          free(temp);
      }

      // Function to print the list
      void printList(struct Node* head) {
          struct Node* temp = head;
          while (temp != NULL) {
              printf("%d -> ", temp->data);
              temp = temp->next;
          }
          printf("NULL\n");
      }

      int main() {
          struct Node* head = NULL;
          struct Node* second = NULL;
          struct Node* third = NULL;

          // Allocate memory for nodes
          head = (struct Node*)malloc(sizeof(struct Node));
          second = (struct Node*)malloc(sizeof(struct Node));
          third = (struct Node*)malloc(sizeof(struct Node));

          // Assign data to nodes
          head->data = 10;
          head->next = second;

          second->data = 20;
          second->next = third;

          third->data = 30;
          third->next = NULL;

          // Deleting the node after the first node (20)
          deleteAfter(head);

          // Print the list
          printf("Linked List: ");
          printList(head);

          return 0;
      }
    
  

Explanation: The `deleteAfter` function deletes the node after the specified node (`prevNode`). It updates the `next` pointer of the previous node to point to the node after the one being deleted, and then frees the memory of the deleted node.

Time Complexity: O(1), since we're directly updating the `next` pointer of the specified node.

Traversing the Linked List

Traversing a linked list involves visiting each node and performing an operation (such as printing the data). You start from the head node and follow the `next` pointers until you reach the end of the list (i.e., a node with a `NULL` pointer).

    
      // Example: Singly Linked List - Traversing in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* next;
      };

      // Function to print the list
      void printList(struct Node* head) {
          struct Node* temp = head;
          while (temp != NULL) {
              printf("%d -> ", temp->data);
              temp = temp->next;
          }
          printf("NULL\n");
      }

      int main() {
          struct Node* head = NULL;
          struct Node* second = NULL;
          struct Node* third = NULL;

          // Allocate memory for nodes
          head = (struct Node*)malloc(sizeof(struct Node));
          second = (struct Node*)malloc(sizeof(struct Node));
          third = (struct Node*)malloc(sizeof(struct Node));

          // Assign data to nodes
          head->data = 10;
          head->next = second;

          second->data = 20;
          second->next = third;

          third->data = 30;
          third->next = NULL;

          // Traversing the list and printing data
          printf("Linked List: ");
          printList(head);

          return 0;
      }
    
  

Explanation: The `printList` function traverses through the linked list by iterating over each node, printing the data until it reaches the end of the list.

Time Complexity: O(n), where n is the number of nodes in the list, as we need to visit each node once.

Searching in Linked List

Searching for a specific node in a singly linked list requires traversing the list from the head to the end and checking the data in each node. If a node with the specified data is found, the search is successful.

    
      // Example: Singly Linked List - Searching in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* next;
      };

      // Function to search for a value in the list
      int search(struct Node* head, int key) {
          struct Node* temp = head;
          while (temp != NULL) {
              if (temp->data == key) {
                  return 1; // Found
              }
              temp = temp->next;
          }
          return 0; // Not found
      }

      int main() {
          struct Node* head = NULL;
          struct Node* second = NULL;
          struct Node* third = NULL;

          // Allocate memory for nodes
          head = (struct Node*)malloc(sizeof(struct Node));
          second = (struct Node*)malloc(sizeof(struct Node));
          third = (struct Node*)malloc(sizeof(struct Node));

          // Assign data to nodes
          head->data = 10;
          head->next = second;

          second->data = 20;
          second->next = third;

          third->data = 30;
          third->next = NULL;

          // Searching for a value
          int key = 20;
          if (search(head, key)) {
              printf("Found %d in the list.\n", key);
          } else {
              printf("%d not found in the list.\n", key);
          }

          return 0;
      }
    
  

Explanation: The `search` function traverses the list, comparing each node’s data with the `key`. If it finds a match, it returns `1` (found), otherwise it returns `0` (not found).

Time Complexity: O(n), where n is the number of nodes in the list, as we may need to check each node.

Doubly Linked List

Doubly Linked List

A Doubly Linked List is a type of linked list in which each node contains two references: - A reference to the next node (`next` pointer) - A reference to the previous node (`prev` pointer) This allows traversal in both directions: from the beginning to the end and vice versa. It enables efficient insertion and deletion from both ends.

Insertion at Beginning

Inserting at the beginning of a doubly linked list involves creating a new node, adjusting the `next` pointer of the new node to the current head, and setting the `prev` pointer of the old head to the new node.

    
      // Example: Doubly Linked List - Insertion at Beginning in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* next;
          struct Node* prev;
      };

      // Function to insert a node at the beginning
      void insertAtBeginning(struct Node** head_ref, int new_data) {
          // Allocate memory for the new node
          struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

          // Assign data to the node
          new_node->data = new_data;

          // Make next of the new node as the head and prev as NULL
          new_node->next = *head_ref;
          new_node->prev = NULL;

          // Change prev of head node to new node
          if (*head_ref != NULL) {
              (*head_ref)->prev = new_node;
          }

          // Move the head to point to the new node
          *head_ref = new_node;
      }

      // Function to print the list
      void printList(struct Node* node) {
          struct Node* last;
          printf("Doubly Linked List: ");
          while (node != NULL) {
              printf("%d <-> ", node->data);
              last = node;
              node = node->next;
          }
          printf("NULL\n");
      }

      int main() {
          struct Node* head = NULL;

          // Inserting at the beginning
          insertAtBeginning(&head, 10);
          insertAtBeginning(&head, 20);
          insertAtBeginning(&head, 30);

          // Printing the list
          printList(head);

          return 0;
      }
    
  

Explanation: In `insertAtBeginning`, a new node is created and inserted at the start. The head pointer is updated to point to the new node. The `prev` pointer of the old head node is also adjusted.

Time Complexity: O(1) because the operation only involves changing a few pointers.

Insertion at End

Inserting at the end of a doubly linked list involves traversing the list to find the last node and then inserting the new node after it by adjusting the pointers of the last node and the new node.

    
      // Example: Doubly Linked List - Insertion at End in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* next;
          struct Node* prev;
      };

      // Function to insert a node at the end
      void insertAtEnd(struct Node** head_ref, int new_data) {
          // Allocate memory for the new node
          struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
          struct Node* last = *head_ref;

          // Assign data to the node
          new_node->data = new_data;
          new_node->next = NULL;

          // If the list is empty, make new node the head
          if (*head_ref == NULL) {
              new_node->prev = NULL;
              *head_ref = new_node;
              return;
          }

          // Traverse to the last node
          while (last->next != NULL) {
              last = last->next;
          }

          // Change the next of last node to the new node
          last->next = new_node;

          // Make the last node the previous of the new node
          new_node->prev = last;
      }

      // Function to print the list
      void printList(struct Node* node) {
          struct Node* last;
          printf("Doubly Linked List: ");
          while (node != NULL) {
              printf("%d <-> ", node->data);
              last = node;
              node = node->next;
          }
          printf("NULL\n");
      }

      int main() {
          struct Node* head = NULL;

          // Inserting at the end
          insertAtEnd(&head, 10);
          insertAtEnd(&head, 20);
          insertAtEnd(&head, 30);

          // Printing the list
          printList(head);

          return 0;
      }
    
  

Explanation: In `insertAtEnd`, we first check if the list is empty. If so, the new node becomes the head. Otherwise, we traverse to the last node, update the last node's `next` pointer to the new node, and set the `prev` pointer of the new node to the last node.

Time Complexity: O(n) where `n` is the number of nodes because we need to traverse the entire list to reach the last node.

Insertion After Specified Node

Inserting after a specified node involves checking that the specified node is not NULL, creating a new node, and updating the pointers of the specified node and the new node.

    
      // Example: Doubly Linked List - Insertion After Specified Node in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* next;
          struct Node* prev;
      };

      // Function to insert a node after a specified node
      void insertAfter(struct Node* prev_node, int new_data) {
          // Check if the previous node is NULL
          if (prev_node == NULL) {
              printf("Previous node cannot be NULL\n");
              return;
          }

          // Allocate memory for the new node
          struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

          // Assign data to the new node
          new_node->data = new_data;

          // Make next of new node as next of prev_node
          new_node->next = prev_node->next;

          // Make next of prev_node as new node
          prev_node->next = new_node;

          // Make prev of new node as prev_node
          new_node->prev = prev_node;

          // Change prev of new node's next node to new node
          if (new_node->next != NULL) {
              new_node->next->prev = new_node;
          }
      }

      // Function to print the list
      void printList(struct Node* node) {
          struct Node* last;
          printf("Doubly Linked List: ");
          while (node != NULL) {
              printf("%d <-> ", node->data);
              last = node;
              node = node->next;
          }
          printf("NULL\n");
      }

      int main() {
          struct Node* head = NULL;

          // Inserting at the beginning and end
          insertAtBeginning(&head, 10);
          insertAtEnd(&head, 20);
          insertAtEnd(&head, 30);

          // Inserting after a specific node (insert 25 after node 20)
          insertAfter(head->next, 25);

          // Printing the list
          printList(head);

          return 0;
      }
    
  

Explanation: The `insertAfter` function inserts a new node after the given `prev_node`. The `next` pointer of the `prev_node` is updated to the new node, and the `prev` pointer of the new node is set to the `prev_node`. We also update the `prev` pointer of the node after the new node.

Time Complexity: O(1) because the operation involves only updating a few pointers, assuming we already have a reference to the node after which we want to insert.

Deletion at Beginning

Deleting a node at the beginning of a doubly linked list involves updating the head pointer to the next node. The `prev` pointer of the new head node (if it exists) is set to NULL.

    
      // Example: Doubly Linked List - Deletion at Beginning in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* next;
          struct Node* prev;
      };

      // Function to delete node at the beginning
      void deleteAtBeginning(struct Node** head_ref) {
          // Check if the list is empty
          if (*head_ref == NULL) {
              printf("List is empty\n");
              return;
          }

          struct Node* temp = *head_ref;

          // Move head to the next node
          *head_ref = temp->next;

          // If the list has more than one node, set prev of new head to NULL
          if (*head_ref != NULL) {
              (*head_ref)->prev = NULL;
          }

          // Free memory of the old head node
          free(temp);
      }

      // Function to print the list
      void printList(struct Node* node) {
          struct Node* last;
          printf("Doubly Linked List: ");
          while (node != NULL) {
              printf("%d <-> ", node->data);
              last = node;
              node = node->next;
          }
          printf("NULL\n");
      }

      int main() {
          struct Node* head = NULL;

          // Code to insert nodes and print the list here...

          // Deleting at the beginning
          deleteAtBeginning(&head);
          printList(head);

          return 0;
      }
    
  

Explanation: The `deleteAtBeginning` function updates the head pointer to point to the second node and frees the memory of the original head.

Time Complexity: O(1), as the operation requires just updating the pointers.

Deletion at End

Deleting a node at the end of a doubly linked list involves traversing to the last node, updating the `next` pointer of the second last node to NULL, and freeing the memory of the last node.

    
      // Example: Doubly Linked List - Deletion at End in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* next;
          struct Node* prev;
      };

      // Function to delete node at the end
      void deleteAtEnd(struct Node** head_ref) {
          // Check if the list is empty
          if (*head_ref == NULL) {
              printf("List is empty\n");
              return;
          }

          struct Node* temp = *head_ref;

          // Traverse to the last node
          while (temp->next != NULL) {
              temp = temp->next;
          }

          // If there's more than one node, adjust the next of the second last node
          if (temp->prev != NULL) {
              temp->prev->next = NULL;
          }

          // If there's only one node, update the head to NULL
          if (temp == *head_ref) {
              *head_ref = NULL;
          }

          // Free memory of the last node
          free(temp);
      }

      // Function to print the list
      void printList(struct Node* node) {
          struct Node* last;
          printf("Doubly Linked List: ");
          while (node != NULL) {
              printf("%d <-> ", node->data);
              last = node;
              node = node->next;
          }
          printf("NULL\n");
      }

      int main() {
          struct Node* head = NULL;

          // Code to insert nodes and print the list here...

          // Deleting at the end
          deleteAtEnd(&head);
          printList(head);

          return 0;
      }
    
  

Explanation: The `deleteAtEnd` function traverses the list to find the last node. Once found, it updates the `prev` pointer of the last but one node to NULL and frees the last node.

Time Complexity: O(n), because you need to traverse the list to reach the last node.

Deletion of Node with Given Data

Deleting a node with specific data involves searching for the node in the list and then adjusting the pointers of the previous and next nodes accordingly.

    
      // Example: Doubly Linked List - Deletion of Node with Given Data in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* next;
          struct Node* prev;
      };

      // Function to delete node with specific data
      void deleteNode(struct Node** head_ref, int key) {
          struct Node* temp = *head_ref;

          // Search for the node with the given data
          while (temp != NULL && temp->data != key) {
              temp = temp->next;
          }

          // If the node is not found
          if (temp == NULL) {
              printf("Node with data %d not found\n", key);
              return;
          }

          // If node is at the beginning
          if (temp == *head_ref) {
              *head_ref = temp->next;
          }

          // Change the prev of the next node
          if (temp->next != NULL) {
              temp->next->prev = temp->prev;
          }

          // Change the next of the previous node
          if (temp->prev != NULL) {
              temp->prev->next = temp->next;
          }

          // Free memory of the node
          free(temp);
      }

      // Function to print the list
      void printList(struct Node* node) {
          struct Node* last;
          printf("Doubly Linked List: ");
          while (node != NULL) {
              printf("%d <-> ", node->data);
              last = node;
              node = node->next;
          }
          printf("NULL\n");
      }

      int main() {
          struct Node* head = NULL;

          // Code to insert nodes and print the list here...

          // Deleting a node with specific data (example: deleting node with data 20)
          deleteNode(&head, 20);
          printList(head);

          return 0;
      }
    
  

Explanation: The `deleteNode` function searches for the node containing the given `key` value. Once found, it updates the pointers of the previous and next nodes to exclude the node being deleted, and then frees its memory.

Time Complexity: O(n) because we have to traverse the list to find the node.

Traversing a Doubly Linked List

Traversing a doubly linked list involves visiting each node starting from the head and going to the last node. Each node contains data and pointers to both the previous and next node.

    
      // Example: Traversing a Doubly Linked List in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* next;
          struct Node* prev;
      };

      // Function to traverse and print the list
      void traverseList(struct Node* head) {
          struct Node* temp = head;
          printf("Doubly Linked List: ");
          
          // Traverse the list
          while (temp != NULL) {
              printf("%d <-> ", temp->data);
              temp = temp->next;
          }
          printf("NULL\n");
      }

      // Function to insert a node at the end (for testing purposes)
      void insertAtEnd(struct Node** head_ref, int new_data) {
          struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
          struct Node* last = *head_ref;

          new_node->data = new_data;
          new_node->next = NULL;

          if (*head_ref == NULL) {
              new_node->prev = NULL;
              *head_ref = new_node;
              return;
          }

          while (last->next != NULL) {
              last = last->next;
          }

          last->next = new_node;
          new_node->prev = last;
      }

      // Main function to test the traversal
      int main() {
          struct Node* head = NULL;

          // Inserting some nodes
          insertAtEnd(&head, 10);
          insertAtEnd(&head, 20);
          insertAtEnd(&head, 30);
          insertAtEnd(&head, 40);
          
          // Traverse and print the list
          traverseList(head);

          return 0;
      }
    
  

Explanation: The `traverseList` function prints the data of each node by moving from the head node through the entire list until it reaches a node with `next` equal to `NULL`.

Time Complexity: O(n), where n is the number of nodes in the list.

Searching in a Doubly Linked List

Searching for a node with a specific data value in a doubly linked list requires traversing through the list and comparing the data of each node with the target value. This is typically done using a linear search.

    
      // Example: Searching in a Doubly Linked List in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* next;
          struct Node* prev;
      };

      // Function to search for a node with a specific value
      struct Node* searchNode(struct Node* head, int key) {
          struct Node* temp = head;
          
          // Traverse the list and search for the node
          while (temp != NULL) {
              if (temp->data == key) {
                  return temp; // Node found
              }
              temp = temp->next;
          }
          
          return NULL; // Node not found
      }

      // Function to insert a node at the end (for testing purposes)
      void insertAtEnd(struct Node** head_ref, int new_data) {
          struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
          struct Node* last = *head_ref;

          new_node->data = new_data;
          new_node->next = NULL;

          if (*head_ref == NULL) {
              new_node->prev = NULL;
              *head_ref = new_node;
              return;
          }

          while (last->next != NULL) {
              last = last->next;
          }

          last->next = new_node;
          new_node->prev = last;
      }

      // Main function to test the search operation
      int main() {
          struct Node* head = NULL;

          // Inserting some nodes
          insertAtEnd(&head, 10);
          insertAtEnd(&head, 20);
          insertAtEnd(&head, 30);
          insertAtEnd(&head, 40);
          
          // Searching for a node with data 20
          struct Node* foundNode = searchNode(head, 20);
          if (foundNode != NULL) {
              printf("Node with data %d found.\n", foundNode->data);
          } else {
              printf("Node not found.\n");
          }

          return 0;
      }
    
  

Explanation: The `searchNode` function traverses the list and checks if the `data` of each node matches the key. If a match is found, it returns the node; otherwise, it returns `NULL`.

Time Complexity: O(n), where n is the number of nodes, since we may need to traverse the entire list to find the node.

Circular Linked List

Circular Linked List - Insertion and Deletion Operations

A Circular Linked List is a variation of a linked list where the last node's next pointer points to the first node. It forms a loop, and you can traverse the list in a circular manner.

Insertion at Beginning

Inserting a new node at the beginning of a circular linked list requires updating the next pointer of the last node to point to the new node, and the new node's next pointer should point to the head.

    
      // Example: Circular Linked List Insertion at Beginning in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* next;
      };

      // Function to insert a node at the beginning of a circular linked list
      void insertAtBeginning(struct Node** head_ref, int new_data) {
          struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
          struct Node* last = *head_ref;

          new_node->data = new_data;
          new_node->next = *head_ref;

          // If the list is empty, the new node points to itself (circular nature)
          if (*head_ref == NULL) {
              *head_ref = new_node;
              new_node->next = *head_ref;
              return;
          }

          // Traverse to the last node
          while (last->next != *head_ref) {
              last = last->next;
          }

          // Change the next of the last node to point to the new node
          last->next = new_node;
          *head_ref = new_node;
      }

      // Function to print the circular linked list
      void printList(struct Node* head) {
          struct Node* temp = head;
          if (head != NULL) {
              do {
                  printf("%d -> ", temp->data);
                  temp = temp->next;
              } while (temp != head);
          }
          printf("HEAD\n");
      }

      // Main function to test
      int main() {
          struct Node* head = NULL;
          
          insertAtBeginning(&head, 10);
          insertAtBeginning(&head, 20);
          insertAtBeginning(&head, 30);
          insertAtBeginning(&head, 40);

          printList(head);

          return 0;
      }
    
  

Insertion at End

Inserting a node at the end of a circular linked list involves finding the last node, updating its next pointer to the new node, and ensuring the new node's next pointer points back to the head.

    
      // Example: Circular Linked List Insertion at End in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* next;
      };

      // Function to insert a node at the end of a circular linked list
      void insertAtEnd(struct Node** head_ref, int new_data) {
          struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
          struct Node* last = *head_ref;

          new_node->data = new_data;
          new_node->next = *head_ref;

          if (*head_ref == NULL) {
              *head_ref = new_node;
              new_node->next = *head_ref;
              return;
          }

          while (last->next != *head_ref) {
              last = last->next;
          }

          last->next = new_node;
      }

      // Function to print the circular linked list
      void printList(struct Node* head) {
          struct Node* temp = head;
          if (head != NULL) {
              do {
                  printf("%d -> ", temp->data);
                  temp = temp->next;
              } while (temp != head);
          }
          printf("HEAD\n");
      }

      // Main function to test
      int main() {
          struct Node* head = NULL;
          
          insertAtEnd(&head, 10);
          insertAtEnd(&head, 20);
          insertAtEnd(&head, 30);
          insertAtEnd(&head, 40);

          printList(head);

          return 0;
      }
    
  

Deletion at Beginning

Deleting the first node in a circular linked list requires updating the next pointer of the last node to point to the second node. After that, the head pointer is updated to point to the second node.

    
      // Example: Circular Linked List Deletion at Beginning in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* next;
      };

      // Function to delete the first node in a circular linked list
      void deleteAtBeginning(struct Node** head_ref) {
          if (*head_ref == NULL) {
              printf("List is empty.\n");
              return;
          }

          struct Node* temp = *head_ref;
          struct Node* last = *head_ref;

          // If there is only one node
          if ((*head_ref)->next == *head_ref) {
              free(*head_ref);
              *head_ref = NULL;
              return;
          }

          // Traverse to the last node
          while (last->next != *head_ref) {
              last = last->next;
          }

          // Update the last node's next pointer
          last->next = (*head_ref)->next;

          // Update the head to the next node
          *head_ref = (*head_ref)->next;
          
          free(temp);
      }

      // Function to print the circular linked list
      void printList(struct Node* head) {
          struct Node* temp = head;
          if (head != NULL) {
              do {
                  printf("%d -> ", temp->data);
                  temp = temp->next;
              } while (temp != head);
          }
          printf("HEAD\n");
      }

      // Main function to test
      int main() {
          struct Node* head = NULL;

          insertAtEnd(&head, 10);
          insertAtEnd(&head, 20);
          insertAtEnd(&head, 30);
          insertAtEnd(&head, 40);

          printList(head);

          // Deleting the first node
          deleteAtBeginning(&head);
          printf("After Deletion at Beginning:\n");
          printList(head);

          return 0;
      }
    
  

Deletion at End

Deleting the last node in a circular linked list requires traversing to the second-to-last node, updating its next pointer to point to the head node, and then freeing the memory of the last node.

  
    // Example: Circular Linked List Deletion at End in C
    #include 
    #include 

    // Node structure
    struct Node {
        int data;
        struct Node* next;
    };

    // Function to delete the last node in a circular linked list
    void deleteAtEnd(struct Node** head_ref) {
        if (*head_ref == NULL) {
            printf("List is empty.\n");
            return;
        }

        struct Node* temp = *head_ref;
        struct Node* prev = NULL;

        // If there is only one node
        if ((*head_ref)->next == *head_ref) {
            free(*head_ref);
            *head_ref = NULL;
            return;
        }

        // Traverse to the last node
        while (temp->next != *head_ref) {
            prev = temp;
            temp = temp->next;
        }

        prev->next = *head_ref; // Update the second-to-last node's next pointer
        free(temp);
    }

    // Function to print the circular linked list
    void printList(struct Node* head) {
        struct Node* temp = head;
        if (head != NULL) {
            do {
                printf("%d -> ", temp->data);
                temp = temp->next;
            } while (temp != head);
        }
        printf("HEAD\n");
    }

    // Main function to test
    int main() {
        struct Node* head = NULL;

        insertAtEnd(&head, 10);
        insertAtEnd(&head, 20);
        insertAtEnd(&head, 30);
        insertAtEnd(&head, 40);

        printList(head);

        // Deleting the last node
        deleteAtEnd(&head);
        printf("After Deletion at End:\n");
        printList(head);

        return 0;
    }
  

Circular Doubly Linked List

Circular Doubly Linked List - Insertion and Deletion Operations

A Circular Doubly Linked List is a variation of the doubly linked list where the last node's next pointer points to the first node, and the first node's prev pointer points to the last node. It forms a loop, allowing traversal in both directions. Here we demonstrate the insertion and deletion operations.

Insertion at Beginning

Inserting a node at the beginning of a circular doubly linked list involves adjusting both the next and prev pointers of the nodes involved. The new node’s next pointer points to the head node, and the head node’s prev pointer points to the new node.

    
      // Example: Circular Doubly Linked List Insertion at Beginning in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* next;
          struct Node* prev;
      };

      // Function to insert a node at the beginning of a circular doubly linked list
      void insertAtBeginning(struct Node** head_ref, int new_data) {
          struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
          struct Node* last = *head_ref;

          new_node->data = new_data;
          new_node->next = *head_ref;
          new_node->prev = last;

          // If the list is empty
          if (*head_ref == NULL) {
              *head_ref = new_node;
              new_node->next = *head_ref;
              new_node->prev = *head_ref;
              return;
          }

          // Update the previous node's next pointer
          last->next = new_node;

          // Update the head to the new node
          *head_ref = new_node;
      }

      // Function to print the circular doubly linked list
      void printList(struct Node* head) {
          struct Node* temp = head;
          if (head != NULL) {
              do {
                  printf("%d <-> ", temp->data);
                  temp = temp->next;
              } while (temp != head);
          }
          printf("HEAD\n");
      }

      // Main function to test
      int main() {
          struct Node* head = NULL;
          
          insertAtBeginning(&head, 10);
          insertAtBeginning(&head, 20);
          insertAtBeginning(&head, 30);
          insertAtBeginning(&head, 40);

          printList(head);

          return 0;
      }
    
  

Insertion at End

Inserting a node at the end of a circular doubly linked list requires updating the next pointer of the last node to point to the new node, and the prev pointer of the new node to point to the last node.

    
      // Example: Circular Doubly Linked List Insertion at End in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* next;
          struct Node* prev;
      };

      // Function to insert a node at the end of a circular doubly linked list
      void insertAtEnd(struct Node** head_ref, int new_data) {
          struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
          struct Node* last = *head_ref;

          new_node->data = new_data;
          new_node->next = *head_ref;
          
          if (*head_ref == NULL) {
              new_node->prev = NULL;
              *head_ref = new_node;
              return;
          }

          while (last->next != *head_ref) {
              last = last->next;
          }

          last->next = new_node;
          new_node->prev = last;
          *head_ref->prev = new_node;
      }

      // Function to print the circular doubly linked list
      void printList(struct Node* head) {
          struct Node* temp = head;
          if (head != NULL) {
              do {
                  printf("%d <-> ", temp->data);
                  temp = temp->next;
              } while (temp != head);
          }
          printf("HEAD\n");
      }

      // Main function to test
      int main() {
          struct Node* head = NULL;
          
          insertAtEnd(&head, 10);
          insertAtEnd(&head, 20);
          insertAtEnd(&head, 30);
          insertAtEnd(&head, 40);

          printList(head);

          return 0;
      }
    
  

Deletion at Beginning

Deleting the first node in a circular doubly linked list requires adjusting the next pointer of the last node to point to the second node and updating the head pointer to the second node.

  
    // Example: Circular Doubly Linked List Deletion at Beginning in C
    #include 
    #include 

    // Node structure
    struct Node {
        int data;
        struct Node* next;
        struct Node* prev;
    };

    // Function to delete the first node in a circular doubly linked list
    void deleteAtBeginning(struct Node** head_ref) {
        if (*head_ref == NULL) {
            printf("List is empty.\n");
            return;
        }

        struct Node* temp = *head_ref;
        struct Node* last = *head_ref;

        // If there is only one node
        if ((*head_ref)->next == *head_ref) {
            free(*head_ref);
            *head_ref = NULL;
            return;
        }

        while (last->next != *head_ref) {
            last = last->next;
        }

        last->next = (*head_ref)->next;
        (*head_ref)->next->prev = last;
        *head_ref = (*head_ref)->next;

        free(temp);
    }

    // Function to print the circular doubly linked list
    void printList(struct Node* head) {
        struct Node* temp = head;
        if (head != NULL) {
            do {
                printf("%d <-> ", temp->data);
                temp = temp->next;
            } while (temp != head);
        }
        printf("HEAD\n");
    }

    // Main function to test
    int main() {
        struct Node* head = NULL;
        
        insertAtEnd(&head, 10);
        insertAtEnd(&head, 20);
        insertAtEnd(&head, 30);
        insertAtEnd(&head, 40);

        printList(head);

        // Deleting the first node
        deleteAtBeginning(&head);
        printf("After Deletion at Beginning:\n");
        printList(head);

        return 0;
    }
  

Deletion at End

Deleting the last node in a circular doubly linked list involves finding the second-to-last node, updating its next pointer to the head, and deleting the last node.

  
    // Example: Circular Doubly Linked List Deletion at End in C
    #include 
    #include 

    // Node structure
    struct Node {
        int data;
        struct Node* next;
        struct Node* prev;
    };

    // Function to delete the last node in a circular doubly linked list
    void deleteAtEnd(struct Node** head_ref) {
        if (*head_ref == NULL) {
            printf("List is empty.\n");
            return;
        }

        struct Node* temp = *head_ref;
        struct Node* last = *head_ref;

        // If there is only one node
        if ((*head_ref)->next == *head_ref) {
            free(*head_ref);
            *head_ref = NULL;
            return;
        }

        while (last->next != *head_ref) {
            last = last->next;
        }

        last->prev->next = *head_ref;
        *head_ref->prev = last->prev;
        free(last);
    }

    // Function to print the circular doubly linked list
    void printList(struct Node* head) {
        struct Node* temp = head;
        if (head != NULL) {
            do {
                printf("%d <-> ", temp->data);
                temp = temp->next;
            } while (temp != head);
        }
        printf("HEAD\n");
    }

    // Main function to test
    int main() {
        struct Node* head = NULL;
        
        insertAtEnd(&head, 10);
        insertAtEnd(&head, 20);
        insertAtEnd(&head, 30);
        insertAtEnd(&head, 40);

        printList(head);

        // Deleting the last node
        deleteAtEnd(&head);
        printf("After Deletion at End:\n");
        printList(head);

        return 0;
    }
  

Binary Tree Traversal

Binary Tree Traversal - Pre-order, In-order, and Post-order

A Binary Tree is a tree data structure in which each node has at most two children, referred to as the left and right child. Traversal in a binary tree means visiting all the nodes in a particular order. There are three primary types of tree traversal:

• Pre-order Traversal
• In-order Traversal
• Post-order Traversal

Pre-order Traversal

Pre-order Traversal visits the nodes in the following order: Root, Left Subtree, Right Subtree. This traversal method is useful for creating a copy of the tree or for prefix expression evaluation.

    
      // Example: Binary Tree Pre-order Traversal in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* left;
          struct Node* right;
      };

      // Function for Pre-order Traversal (Root, Left, Right)
      void preOrder(struct Node* root) {
          if (root == NULL) {
              return;
          }
          printf("%d ", root->data); // Visit root
          preOrder(root->left);      // Traverse left subtree
          preOrder(root->right);     // Traverse right subtree
      }

      // Function to create a new node
      struct Node* newNode(int data) {
          struct Node* node = (struct Node*)malloc(sizeof(struct Node));
          node->data = data;
          node->left = node->right = NULL;
          return node;
      }

      int main() {
          struct Node* root = newNode(1);
          root->left = newNode(2);
          root->right = newNode(3);
          root->left->left = newNode(4);
          root->left->right = newNode(5);

          printf("Pre-order Traversal: ");
          preOrder(root); // Output: 1 2 4 5 3
          return 0;
      }
    
  

In-order Traversal

In-order Traversal visits the nodes in the following order: Left Subtree, Root, Right Subtree. This traversal is commonly used for binary search trees (BST), as it visits nodes in ascending order.

    
      // Example: Binary Tree In-order Traversal in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* left;
          struct Node* right;
      };

      // Function for In-order Traversal (Left, Root, Right)
      void inOrder(struct Node* root) {
          if (root == NULL) {
              return;
          }
          inOrder(root->left);     // Traverse left subtree
          printf("%d ", root->data); // Visit root
          inOrder(root->right);    // Traverse right subtree
      }

      // Function to create a new node
      struct Node* newNode(int data) {
          struct Node* node = (struct Node*)malloc(sizeof(struct Node));
          node->data = data;
          node->left = node->right = NULL;
          return node;
      }

      int main() {
          struct Node* root = newNode(1);
          root->left = newNode(2);
          root->right = newNode(3);
          root->left->left = newNode(4);
          root->left->right = newNode(5);

          printf("In-order Traversal: ");
          inOrder(root); // Output: 4 2 5 1 3
          return 0;
      }
    
  

Post-order Traversal

Post-order Traversal visits the nodes in the following order: Left Subtree, Right Subtree, Root. This traversal method is useful for deletion of the tree or postfix expression evaluation.

    
      // Example: Binary Tree Post-order Traversal in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* left;
          struct Node* right;
      };

      // Function for Post-order Traversal (Left, Right, Root)
      void postOrder(struct Node* root) {
          if (root == NULL) {
              return;
          }
          postOrder(root->left);     // Traverse left subtree
          postOrder(root->right);    // Traverse right subtree
          printf("%d ", root->data); // Visit root
      }

      // Function to create a new node
      struct Node* newNode(int data) {
          struct Node* node = (struct Node*)malloc(sizeof(struct Node));
          node->data = data;
          node->left = node->right = NULL;
          return node;
      }

      int main() {
          struct Node* root = newNode(1);
          root->left = newNode(2);
          root->right = newNode(3);
          root->left->left = newNode(4);
          root->left->right = newNode(5);

          printf("Post-order Traversal: ");
          postOrder(root); // Output: 4 5 2 3 1
          return 0;
      }
    
  

Binary Search Tree (BST)

Binary Search Tree (BST) Operations

A Binary Search Tree (BST) is a binary tree where each node has at most two children and the left child’s value is less than the parent node’s value, while the right child’s value is greater. This property allows for efficient searching, insertion, and deletion of nodes in the tree.

Searching in BST

Searching in a Binary Search Tree is a process of finding a specific value in the tree by comparing the search key with the node’s value. If the key is less, we move to the left child, and if the key is greater, we move to the right child.

    
      // Example: Searching in BST in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* left;
          struct Node* right;
      };

      // Function to search a key in the BST
      struct Node* search(struct Node* root, int key) {
          if (root == NULL || root->data == key) {
              return root;
          }
          if (key < root->data) {
              return search(root->left, key); // Search in left subtree
          }
          return search(root->right, key); // Search in right subtree
      }

      // Function to create a new node
      struct Node* newNode(int data) {
          struct Node* node = (struct Node*)malloc(sizeof(struct Node));
          node->data = data;
          node->left = node->right = NULL;
          return node;
      }

      int main() {
          struct Node* root = newNode(50);
          root->left = newNode(30);
          root->right = newNode(70);
          root->left->left = newNode(20);
          root->left->right = newNode(40);
          root->right->left = newNode(60);
          root->right->right = newNode(80);

          int key = 40;
          struct Node* result = search(root, key);
          if (result != NULL) {
              printf("Node with key %d found.\n", key);
          } else {
              printf("Node with key %d not found.\n", key);
          }
          return 0;
      }
    
  

Insertion in BST

Insertion in a Binary Search Tree involves placing a new node in the correct position based on the BST property: if the new key is less than the current node’s key, it goes to the left subtree; otherwise, it goes to the right.

    
      // Example: Insertion in BST in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* left;
          struct Node* right;
      };

      // Function to insert a key into the BST
      struct Node* insert(struct Node* root, int key) {
          if (root == NULL) {
              return newNode(key); // Create a new node if root is NULL
          }

          if (key < root->data) {
              root->left = insert(root->left, key); // Insert in the left subtree
          } else {
              root->right = insert(root->right, key); // Insert in the right subtree
          }
          return root;
      }

      // Function to create a new node
      struct Node* newNode(int data) {
          struct Node* node = (struct Node*)malloc(sizeof(struct Node));
          node->data = data;
          node->left = node->right = NULL;
          return node;
      }

      int main() {
          struct Node* root = NULL;

          // Insert nodes into the BST
          root = insert(root, 50);
          root = insert(root, 30);
          root = insert(root, 70);
          root = insert(root, 20);
          root = insert(root, 40);
          root = insert(root, 60);
          root = insert(root, 80);

          printf("BST after insertion: ");
          inOrder(root); // Output will show nodes in ascending order
          return 0;
      }
    
  

Deletion in BST

Deletion in a Binary Search Tree is a more complex operation because you have three cases to handle:

• If the node has no children (leaf node), simply remove the node.
• If the node has one child, remove the node and connect the child with its parent.
• If the node has two children, replace the node with its in-order successor (smallest node in the right subtree) or in-order predecessor (largest node in the left subtree).

    
      // Example: Deletion in BST in C
      #include 
      #include 

      // Node structure
      struct Node {
          int data;
          struct Node* left;
          struct Node* right;
      };

      // Function to find the minimum node in a given BST
      struct Node* minValueNode(struct Node* node) {
          struct Node* current = node;
          while (current && current->left != NULL) {
              current = current->left; // Keep going left
          }
          return current;
      }

      // Function to delete a key in the BST
      struct Node* deleteNode(struct Node* root, int key) {
          if (root == NULL) {
              return root;
          }

          if (key < root->data) {
              root->left = deleteNode(root->left, key); // Search in the left subtree
          } else if (key > root->data) {
              root->right = deleteNode(root->right, key); // Search in the right subtree
          } else {
              // Node to be deleted has one or no child
              if (root->left == NULL) {
                  struct Node* temp = root->right;
                  free(root);
                  return temp;
              } else if (root->right == NULL) {
                  struct Node* temp = root->left;
                  free(root);
                  return temp;
              }

              // Node to be deleted has two children, get the inorder successor
              struct Node* temp = minValueNode(root->right);

              // Copy the inorder successor's content to this node
              root->data = temp->data;

              // Delete the inorder successor
              root->right = deleteNode(root->right, temp->data);
          }
          return root;
      }

      // Function to create a new node
      struct Node* newNode(int data) {
          struct Node* node = (struct Node*)malloc(sizeof(struct Node));
          node->data = data;
          node->left = node->right = NULL;
          return node;
      }

      // In-order Traversal to display BST
      void inOrder(struct Node* root) {
          if (root == NULL) {
              return;
          }
          inOrder(root->left); // Traverse left subtree
          printf("%d ", root->data); // Visit root
          inOrder(root->right); // Traverse right subtree
      }

      int main() {
          struct Node* root = NULL;

          // Insert nodes into the BST
          root = insert(root, 50);
          root = insert(root, 30);
          root = insert(root, 70);
          root = insert(root, 20);
          root = insert(root, 40);
          root = insert(root, 60);
          root = insert(root, 80);

          printf("BST before deletion: ");
          inOrder(root); // Output: 20 30 40 50 60 70 80

          // Delete node with key 20
          root = deleteNode(root, 20);
          printf("\nBST after deleting 20: ");
          inOrder(root); // Output: 30 40 50 60 70 80

          return 0;
      }
    
  

AVL Tree Operations

Insertion in AVL Tree

AVL Tree insertion is similar to standard BST insertion. After inserting a node, we check if the tree has become unbalanced and perform the necessary rotation to restore balance.

a) LL Rotation (Left-Left)

LL Rotation occurs when the left subtree of the left child is too deep. To restore balance, we perform a single right rotation.

    
      // Example: LL Rotation in AVL Tree (Right Rotation)
      #include 
      #include 

      // Node structure for AVL Tree
      struct Node {
          int data;
          struct Node* left;
          struct Node* right;
          int height;
      };

      // Function to get the height of the node
      int height(struct Node* node) {
          if (node == NULL) return 0;
          return node->height;
      }

      // Function to get the balance factor of the node
      int getBalance(struct Node* node) {
          if (node == NULL) return 0;
          return height(node->left) - height(node->right);
      }

      // Right rotation (LL Rotation)
      struct Node* rightRotate(struct Node* y) {
          struct Node* x = y->left;
          struct Node* T2 = x->right;

          // Perform rotation
          x->right = y;
          y->left = T2;

          // Update heights
          y->height = 1 + (height(y->left) > height(y->right) ? height(y->left) : height(y->right));
          x->height = 1 + (height(x->left) > height(x->right) ? height(x->left) : height(x->right));

          return x; // Return new root
      }
    
  

b) LR Rotation (Left-Right)

LR Rotation occurs when the left child’s right subtree is too deep. This requires a left rotation followed by a right rotation to balance the tree.

  
// Example: LR Rotation in AVL Tree
#include 
#include 

// Left Rotation (part of LR rotation)
struct Node* leftRotate(struct Node* x) {
    struct Node* y = x->right;
    struct Node* T2 = y->left;

    // Perform rotation
    y->left = x;
    x->right = T2;

    // Update heights
    x->height = 1 + (height(x->left) > height(x->right) ? height(x->left) : height(x->right));
    y->height = 1 + (height(y->left) > height(y->right) ? height(y->left) : height(y->right));

    return y; // Return new root
}

// Right then left rotation (LR Rotation)
struct Node* leftRightRotate(struct Node* node) {
    node->left = leftRotate(node->left);
    return rightRotate(node);
}
  

c) RL Rotation (Right-Left)

RL Rotation occurs when the right child’s left subtree is too deep. This requires a right rotation followed by a left rotation.

  
// Example: RL Rotation in AVL Tree
#include 
#include 

// Left Rotation (part of RL rotation)
struct Node* leftRotate(struct Node* x) {
    struct Node* y = x->right;
    struct Node* T2 = y->left;

    // Perform rotation
    y->left = x;
    x->right = T2;

    // Update heights
    x->height = 1 + (height(x->left) > height(x->right) ? height(x->left) : height(x->right));
    y->height = 1 + (height(y->left) > height(y->right) ? height(y->left) : height(y->right));

    return y; // Return new root
}

// Right Rotation (part of RL rotation)
struct Node* rightRotate(struct Node* y) {
    struct Node* x = y->left;
    struct Node* T2 = x->right;

    // Perform rotation
    x->right = y;
    y->left = T2;

    // Update heights
    y->height = 1 + (height(y->left) > height(y->right) ? height(y->left) : height(y->right));
    x->height = 1 + (height(x->left) > height(x->right) ? height(x->left) : height(x->right));

    return x; // Return new root
}

// Left then right rotation (RL Rotation)
struct Node* rightLeftRotate(struct Node* node) {
    node->right = rightRotate(node->right);
    return leftRotate(node);
}
  

d) RR Rotation (Right-Right)

RR Rotation occurs when the right subtree of the right child is too deep. To restore balance, we perform a left rotation.

  
// Example: RR Rotation in AVL Tree (Left Rotation)
#include 
#include 

// Left Rotation (RR Rotation)
struct Node* leftRotate(struct Node* x) {
    struct Node* y = x->right;
    struct Node* T2 = y->left;

    // Perform rotation
    y->left = x;
    x->right = T2;

    // Update heights
    x->height = 1 + (height(x->left) > height(x->right) ? height(x->left) : height(x->right));
    y->height = 1 + (height(y->left) > height(y->right) ? height(y->left) : height(y->right));

    return y; // Return new root
}
  

Deletion in AVL Tree

Deletion in AVL Tree involves deleting a node as in a regular binary search tree, followed by checking for any imbalance. If the tree becomes unbalanced, appropriate rotations (LL, LR, RL, or RR) are performed to restore balance.

  
// Example: Deletion in AVL Tree
#include 
#include 

// Function to delete a node and balance the tree
struct Node* deleteNode(struct Node* root, int key) {
    if (root == NULL) {
        return root;
    }

    if (key < root->data) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->data) {
        root->right = deleteNode(root->right, key);
    } else {
        // Node to be deleted has one or no child
        if (root->left == NULL) {
            struct Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            struct Node* temp = root->left;
            free(root);
            return temp;
        }

        // Node has two children, get the inorder successor
        struct Node* temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }

    // Update the height of the current node
    root->height = 1 + (height(root->left) > height(root->right) ? height(root->left) : height(root->right));

    // Get the balance factor
    int balance = getBalance(root);

    // If the node is unbalanced, perform rotations
    if (balance > 1 && getBalance(root->left) >= 0) {
        return rightRotate(root); // LL
    }

    if (balance > 1 && getBalance(root->left) < 0) {
        return leftRightRotate(root); // LR
    }

    if (balance < -1 && getBalance(root->right) <= 0) {
        return leftRotate(root); // RR
    }

    if (balance < -1 && getBalance(root->right) > 0) {
        return rightLeftRotate(root); // RL
    }

    return root;
}